Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammars
Authors: Kaiyue Wen
Yuchen Li
Bingbin Liu
Andrej Risteski
Venue: NeurIPS 2023 poster (2023)
Keywords: Transformer
Self Attention
Dyck Language
Context Free Grammar
Formal Language
Theory
Interpretability
TL;DR: By a combination of theory and experiments on synthetic and real data, we show that interpretability claims based on individual heads or weight matrices in the transformer can be misleading.

Abstract: Transformer interpretability aims to understand the algorithm implemented by a learned Transformer by examining various aspects of the model, such as the weight matrices or the attention patterns.
In this work, through a combination of theoretical results and carefully controlled experiments on synthetic data, we take a critical view
of methods that exclusively focus on individual parts of the model, rather than consider the network as a whole.
We consider a simple synthetic setup of learning a (bounded) Dyck language. Theoretically, we show that the set of models that (exactly or approximately) solve this task satisfy a structural characterization derived from ideas in formal languages (the pumping lemma).
We use this characterization to show that the set of optima is qualitatively rich; in particular, the attention pattern of a single layer can be "nearly randomized", while preserving the functionality of the network.
We also show via extensive experiments that these constructions are not merely a theoretical artifact: even with severe constraints to the architecture of the model, vastly different solutions can be reached via standard training. Thus, interpretability claims based on inspecting individual heads or weight matrices in the Transformer can be misleading.

Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammars
Kaiyue Wen Tsinghua University
Yuchen Li
Camegie Mellon University yuchen140cs. cmu. edu
wenky200mails tsinghua. edu. on
Bingbin Liu
Andrej Risteski Carnegie Mellon University aristesk@andrev. cmu, edu
Cameeiic Mellon University bingbinl@cs. cmu, edu
Abstract
Transformer interpretability aims to understand the algorithm implemented by learned Transformer by examining various aspects of the model, such as the weight matrices the attention patterns. In this work, through combination theoretical results and carefully controlled experiments on synthetic data, we take a critical view of methods that exclusively focus on individual parts of the model, rather than consider the network as a whole. We consider a simple synthetic show that the
setup of learning (bounded) Dyck language. Theoretically, set of models that (exactly or approximately) solve this task satisfy a structural characterization derived from ideas in formal languages (the pumping lemma). We use this characterization to show that the set of optima is qualitatively rich; in particular, the attention pattern of single layer be "nearly randomized", while preserving the functionality of the network. We also show via extensive experiments that these constructions severe constraints to the architecture of the model, vastly different solutions can be reached via standard training. Thus, interpretability claims based on inspecting individual heads or weight matrices in the Transformer can be misleading.
not merely theoretical artifact: even with
Introduction
Transformer based models power many leading approaches to natural language processing. With their growing deployment in various applications, it is increasingly essential to understand the inner working these models. Towards addressing this, there have been great advancement in the field of interpretability presenting various types of evidence (Clark et al. 2019: Vig & Belinkov 2019 Wiegreffe & Pinter, 2019) Nanda et al. 2023 Wang et al.] 2003), some of which, however, can be misleading despite being highly intuitive (Jain & Wallace 2019 Serrano & Smith 2019 Rogers
ct al. 2020 Grimsley et al. 2020 Brunner et al. 2020: Meister et al. 2021).
In this work, aim to understand the theoretical limitation of certain interpretability methods by characterizing the set of viable solutions. We focus on myopic interpretability methods, i.e. methods based on examining individual components only. We adopt a particular toy setup in which Transformers are trained to generate Dyck grammars, a classic type of formal language grammar consisting of balanced parentheses of multiple types. Dyck is useful sandbox, as it captures properties like long-range dependency and hierarchical tree-like structure that commonly appear in natural and programming language syntax, and has been object of interest in many theoretical studies (Hahn 2020 Yao et al. 2021 Liu et al.) 2022b 2023 Dyck is canonically parsed using
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(a) With Position Embedding
(b) With Position
(c) Without Position
(d) Without Position Embedding
Embedding
Embedding
Figure 1: Second-layer attention patterns of two-layer Transformers on Dyck: typical attention
patterns do not exactly match the intuitively interpretable stack-like pattern prescribed in Ebrahimi al. (2020); Yao al. (202T). The blue boxes indicate the locations of the last unmatched open brackets, as they would appear in back-like pattern. All models reach 2 97% accuracy (defined in Section 4.1 the heatmap. darker color indicates larger value.
a stack-like data structure. Such stack-like patterns (Figure T have been observed in the attention heads (Ebrahimi et al. 2020). which was later bolstered by mathematical analysis in Yao et al. (2021).
From a representational perspective and via explicit constructions of Transformer weights, recent work (Liu et al. 2023 Li et al. 2023) show that Transformers are sufficiently expressive to admit very different solutions that perform equally well on the training distribution. Thus, the following questions naturally arise:
(Q1) Do Transformer solutions found empirically match the theoretical constructions given in these representational results (Figure ? In particular, are interpretable stack-like pattern in Ebrahimi et al. (2020) the norm or the exception in practice?
(Q2) More broadly, can we understand in principled manner the fundamental obstructions to reliably "reverse engineering" the algorithm implemented by a Transformer by looking at individual attention patterns?
(Q3) Among models that perform (near- Joptimally on the training distribution, even if we cannot fully reverse engineer the algorithm implemented by the learned solutions, identify properties that characterize performance beyond the training distribution?
Our contributions. We first prove several theoretical results to provide evidence for why individual components (c.g. attention patterns or weights) of a Transformer should not be expected to be interpretable. In particular, prove:
A perfect balance condition (Theorem M on the attention pattern that is sufficient and necessary for 2-layer Transformers with minimal first layer (Assumption) D to predict optimally on Dyck of any length. We then show that this condition permits abundant non-stack-like attention patterns that do not necessarily reflect any structure of the task, including uniform attentions (Corollary [
An approximate balance condition (Theorem 3). the near-optimal counterpart of the condition above, for predicting on bounded-lente -engtt Dyck. Likewise, non-stack-like attention patterns exist. Indistinguishability from a single component (Theorem 2}. proved via a Lottery Ticket Hypothexis style argument that any Transformer can be approximated by pruning larger random Transformer, implying that interpretations based exclusively on local components may unreliable.
We further accompany these theoretical findings with an extensive set of empirical investigations.
Is standard training biased towards interpretable solutions? While both stack-like and non-stack like patterns can process Dyck theoretically, the inductive biases the architecture or the optimization process may prefer one solution over the other in practice. In Section 4.1 based on wide range of Dyck distributions and model architecture ablations, we find that Transformers that generalize near-perfectly in in-distribution (and reasonably well out-of- dittr--distribution) do not typically produce stack-like attention patterns, showing that the results reported in prior work (Ebrahimi et al. 2020)
should not be expected from standard training.
Do non-interpretable solutions perform well in pructice? Our theory predicts that balanced (or even uniform) attentions suffice for good in- and out-of-disttriuutio generalization. In Section 4.2

---

empirically verify that with standard training, the extent to which attentions are balanced is positively correlated with generalization performance. Moreover, we can guide Transformers to learn more balanced attention by regularizing for the balance condition, leading to better length generalization.
1.1 Related Work
There has been a flourishing line of work on interpretability in natural language processing. Multiple "probing" tasks have been designed to extract syntactic or semantic information from the learned
representations (Raganato & Tiedemann 2018 Liu et al. 2019 Hewitt & Manning 2019 Clark et al.) 2019). However, the effectiveness of probing often intricately depend on the architecture choices and task design, and sometimes may even result in misleading conclusions (Jain & Wallace 2019
Serrano & Smith 2019 Rogers et al. 2020; Brunner et al. 2020 Prasanna et al.] Meister
Meister et al.
2021). While these challenges do not completely invalidate existing approaches (Wiegreffe & Pinter 2019 it does highlight the need for more rigorous understanding of interpretability.
Towards this, choose focus the synthetic setup of Dyck whose solution space is easier to characterize than natural languages, allowing us to identify a set of feasible solutions. While similar representational results have been studied in prior work (Yao et al., [2021] [iu et al. [2223] Zhao et al., 2023), our work emphasizes that theoretical constructions do not resemble the solutions found in practice. Moreover, the multiplicity of valid constructions suggest that understanding Transformer solutions require analyzing the optimization process, which a number of prior work has made progress
on (Jelassi et al. 2022 Li al. 2023 Deng al. 2023).
Finally, it is worth noting that the challenges highlighted in our work do not contradict the line of prior work that aim to improve mechanistic interpretability into trained model the training process
(Elhage et al. 2021 Olsson et al. 2022; Nanda et al., 2023 Chughtai et al. 2023 Li et al. (023).
which aim to develop circuit-level understanding of particular model or the training process.
We defer discussion on additional related work to Appendix
2 Problem Setup
Dyck languages A Dyck language (Schützenberger,, 1963) is generated by a context-free grammar, where the valid strings consist of balanced brackets of different types (for example, "[O]" is valid but "(D]" is not). Dyck, denote the Dyck language defined on k types of brackets. The alphabet of Dyck, denoted as [2k] {1, 2, ... 2k), where for each type t [k], tokens 2t and 2# are a pair of corresponding open and closed brackets. Dyck languages can be recognized by push-down automaton. For string wr and < j E Z,. we use Wey to denote the substring of w between position i and position (both ends included). For valid prefix Wis,, the grammar depth of wii is defined as the depth of the stack after processing wiss
depth(w1::) = # #Open Brackets in W1: #Closed Brackets in wiss-
We overload depth (11)) to also denote the grammar depth of the bracket at position i. For example, in each pair of matching brackets, the closing bracket is one depth smaller than the open bracket. We will use Ti to denote a token of type i [2k] placed at grammar depth d E N.
We consider bounded-depth Dyck languages following Yao et al. 1b. Specifically, Dyck is subset of Dyck, such that the depth of any prefix of word bounded by D,
Dycks,p == (Wi.n Dyck, mmx depth(w).:) < D). :E(n)
While bounded grammar depth might seem restrictive. suffices to capture many practical settings, For example, the level of recursion occurring in natural languages is typically bounded by small constant (Karlsson 2007 Jin et al. 2018). We further define the length-N prefix set of Dyck as
Dyck (WiNN
3n 2 N, WN Imn E [2A]=-N s.l. Winn E Dyckk,D)-
Our theoretical setup uses the following data distribution DAN,D,N Definition (Dyck distribution). The distribution D Da,,DDN, specified by g E (0, 1), is defined over Dyck such that VWI.N E Dyck
I((LN) xc k)/k) # (1)pc is opon, depth(un:.))> >> (1 #) (ilw; is closed depth (w..))
(3)
3

---

That is, q (0, 1) denote the probability of seeing open bracket at the next position, except for two corner cases: 1) the next bracket has be open if the current grammar depth is after seeing the open bracket); 2) the next bracket has to be closed if the current grammar depth is D.
Training Objectives. Given model fo parameterized by 0, we train with next-token prediction language modeling objective on a given D.N. Precisely, given a loss function I(-,-) - R, fo is trained minimize the loss function ming L(0; D.N. with
((0:DgA.D.N) N DON.D
Σ ((f)(w)==))
in which =(w;) {0, 2 denotes the one-hot embedding of token wy. We will omit the distribution D.N when it is clear from the context. We will also consider a éy-regularized version _ (0)
[()) + X i with parameter À > 0.
For our theory, we will consider the mean squared error as the loss function:
I == (1r z:)
|| z4 122
(5)
In our experiments, we apply the cross entropy loss following common practice.
Transformer Architecture. We consider a general formulation of Transformer in this work: the 1-th layer is parameterized by 0()) := (W w((O, Rm xm, and w E R are the key, query, and value matrices of the attention module; param(g!)) are parameters of ford-forward network g(d), consisting of fully connected layers, (optionally) LayerNorms and residual links. Given X E iRmxN, the matrix of m-dimensional features on length-N sequence, the 1-th layer of Transformer computes the function
K w param(g!))) E O, where w will E K
fi(X; =g (LN W X o (c (W x) ( ( + +x).
(6)
atiention puttern
exp(As.) where is the column-wise softmax operation defined oAA), ΣY exp(Ax.))" C is the causal mask matrix defined as Ci. = - inf in; > j] where inf denotes infinity. We call
(c+ (w K x) ( the Attention Pattern of the Transformer layer 1. LN represents column- wise LayerNorm operation, whose jeh output column is defined
PIA. INCI, (A) max Maxx||PPAA, 12. CLN) PL = Im 11
m
Here P1 denotes the projection orthogonal to the 11 subspace and CLN is called the normalizing constant for LayerNorm.
We will further define the attention output at the 1-th layer as
au (X; (())00)) - Xo (c (W x) (W x)).
(8)
When CLN O, we will also consider the unnormalized attention output as
āz (x;;((() =w xo (c (W X) (w2" x))
(9)
where 5(A)..) = (A,)) and it holds by definition that LND (ār 0)) = ((()).(
L-layer Transformer Tr consists of a composition of of the above layers, along with a word embedding matrix Wg E m and a linear decoding head with weight WHead E 2 When
'The challenge of applying our theory to cross cotsoyy loss is that for some prefixes, their grammatical immediate continuations strictly exclude certain tokens in the vocabulary (e.g. "I" cannot immediately follow "("), so the optimal cross-entropy loss can only be attained if some parameters are set to infinity. However, when label smoothing is added, the optima is finite again, and analysis similar to ours could apply. this just compact way write the standard mean subtraction operation

---

inputting a sequence of tokens into Transformer, we will append a starting token ts that is distinct from any token in the language at the beginning of the sequence. Let Z E [2*x(N+1) denote the one-hot embedding of length-N sequence, then Tr computes for Z
T(2) = WHead St. (/i (W=2))) (1.x2))(((Wx2)))) I:2x,(N+1)
(10)
Theoretical Analyses
Many prior works have looked for intuitive interpretations of Transformer solutions by studying the attention patterns of particular heads or some individual components of Transformer (Clark jtt al. 2019 Vig & Belinkov 2019 Dar et al. (022). However, we show in this section why this methodology can be insufficient even for the simple setting of Dyck. Namely, for Transformers that generalize well on Dyck (both in-distribution and -ff-iisirbuutinn) neither attention patterns nor individual local components are guaranteed to encode structures specific for parsing Dyck. We further argue that the converse is also insufficient: when a Transformer does produce interpretable attention patterns, there could be limitations of such interpretation as well, as discussed in Appendix Together, our results provide theoretical evidence that careful analyses (beyond heuristics) are required when interpreting the components of learned Transformer.
3.1 Interpretability Requires Inspecting More Than Attention Patterns
This section focuses Transformers with layers, which are sufficient for processing Dyck Yao et al. 202T). We will show that even under this simplified setting, attention patterns alone are not sufficient for interpretation. In fact, we will further restrict the of 2-layer Transformers by requiring the first-layer outputs to only depend on information necessary for processing Dyck:
Assumption 1 (Minimal First Layer). We consider 2-layer Transformers with a minimal first layer ft. That is, let Z E (X+ denote the one-hot embeddings of any input sequence Is, 1s,,,,..,,, [2k), then the (j + 1)th column of the oulput ('( Z) only depends on the type and depth of 1g. Vj E [N].
Assumption[[]eee Trequires the first layer output to depend only on the bracket type and depth, disregarding any other information such positions; such example is given by Yao et al. (2021). The construction minimal first layer can vary, hence we directly parameterize its output instead:
Definition (Minimal first layer embeddings). Given a minimal first layer, e(Tr,a) E R. denotes its output embedding of Te.d a for E [28), [D]. e(ts) E Th is the embedding of the starting token.
It is important to note that while the minimal first layer is strong condition, it does not weaken our results: We will show that the function class allows for a rich set of solutions, none of which are necessarily interpretable. Relaxing to more complex classes will only expand the solution set, and hence our conclusion will remain valid. See Appendix C.2 for more technical details.
3.1.1 Perfect Balance Condition: Ideal Generalization of Unbounded Length
Some prior works have tried to understand the model by inspecting the attention patterns (Ebrahimi al. 2020 Clark al., 2019 Vig & Belinkov (019)). However, we will show that the attention patterns alone are too flexible to be helpful, even for the restricted class of a 2-layer Transformer with minimal first layer (Assumption [T and even on language as simple Dyck. In particular, the Transformer only needs to satisfy what we call the balanced condition:
Definition 3 (Balance condition), A 2-layer Transformer (Equation (00 with a minimal first layer (Assumption 7 and Definition ( d', d,, d2 E D..
said to satisfy the balance condition, if for any i, E [R]] and
(e(T2--1,))) - e(F2)dr1)) (W() Tw! (e(Tz),,,)) e(T2ja.d)) 0.
(11)
The following result shows that under minor conditions the balance condition is both necessary and sufficient:
5

---

Theorem 1 (Perfect Balance), Consider a two-layer Transformer T (Equation (TO)) with minimal
first layer (Assumption 7 and CLN (Equation (7). Let O denote the optimal prediction scenario, that is, when the first layer embeddings {e(Ti,a) de dE (),NE)2 (Definition 2 and second layer parameters ((2) satisfy
= de()),E))) 2 arg min L(O; D,,,DDN), VN,
where the objective C is defined in Equation 4 Then,
Equation
a necessary condition of O, if W satisfies Pi W V e(Tr.a) + 0, VL E [b], E [D].
(2)
a sufficient condition of O, if the set of 2k + encodings (e(T2i-1,d) el e(T2s,d) U (e(ts)) are linearly independent for any d E (D), and the projection
Equation
Sunction g(2 (2) 6-layer MIP with O(k2 D²) width.
Remark: Recall from Equation that P1 projects to the subspace orthogonal 11 The assumption in the necessary condition can be intuitively understood as requiring all tokens to have nonzero contributions the prediction after the LayerNorm.
Recall that e(T2--1.d e( denote the first-layer outputs for a matching pair of brackets. Intuitively, Equation [1] says that since matching brackets should not affect future predictions, their embeddings should balance out each other. The balance condition Equation (TT) "perfect" the sense that the theory assumes the model can minimize the loss for any length N; we will see an approximate version later in Theorem
Proof of the necessity of the balance condition. The key idea is reminiscent of the pumping lemma for regular languages. For any prefix p ending with a closed bracket Taj.d for d 2 and containing brackets of all depths in [D], let p3 be the prefix obtained by inserting pairs of { d2i,d' for arbitrary E [k]] and d' E [D]. Denote the projection of the unnormalized attention output by
d1 Ta2,da) = Pa exp (e(Tr.a)) (W Tw? e(Tr..s)) W eTT...).
(12)
We ignored the normalization in softmax above, since the attention output will normalized directly by LayerNorm according to Equation (6)
By Equation TO.. there exists vector R such that for any B N, the next-token logits given are
by Transformer T
V + (u( Thi," + u (T22,d1 72: 724-1
e(Tzsa)). (13)
T(ps)= = WHeadg
|| + 3 (u( (T(22j,d, T2id" + u (T22.dd T2- 1,4
The proof proceeds by showing a contradiction. Suppose TT d. 72, Based on the continuity of the projection function and the LayerNorm Layer, we show that lim (pps) depend only on grammar depths d, d' and types 2j, 2i - 1, 2i. However, these are not sufficient to determine the next-token probability from Pa. since the latter depends the type of the last unmatched open bracket in p. This contradicts the assumption that the model can minimize the loss for any length N. Hence must have
ul 7,a) * 0.
u(T2j,d, T2r.d 11 + u(T22.d 1.d) = O.
(14)
Finally, as we assumed that P1 W. v (Tr.)) # O, we conclude that
[P Wye (12 112 (2 (T25+1.) = In ( ( Wye (T2i-1.0) 1|2
(e (F2--1d))) - (f2) (w (2)
K
where the right hand side is independent of j, d, concluding the proof for necessity. The proof of sufficiency are given in Appendix C.I
"The layers are by our construction. We will first use 4 layers to convert input of the projection function to a triplet indicating the type and depth of the last token and the type of the last unmatched bracket when the last token is a closed bracket. We will then use another 2 layers to predict the next token probability based on the triplet. This construction may be improved.

---

Note that the perfect balance condition is an orthogonal consideration to interpretability. For example, even the uniform attention satisfies the condition and can solve Dyck:
Corollary 1. There exists 2-layer Transformer with uniform attention and no position embedding (but with causal mask and a starting token that generates the Dyck language of arbitrary length.
Since uniform attention patterns are hardly reflective of any structure of Dyck, Corollary ! proves that attention patterns can be oblivious about the underlying task, violating the "faithfulness' criteria for interpretation (Jain & Wallace 2019h. We will further show in Appendix [B.]] that empirically, seemingly structured attention patterns may not accurately represent the inherent structure of the task.
Extension to approximate balance condition: Theorem 1 assumes the model reaches the optimal loss for Dyck prefixes of any length. However, in practice, due finite samples and various sources of randomness, training often does not end exactly at population optima. In this case, the condition in Theorem is not precisely met. However, even for models that approximately meet those conditions, we will prove that when the second-layer projection function g(2) is Lipschitz, a similar condition as in Equation (14) is still necessary. Details are deferred to Appendix C.4
3.2 Interpretability Requires Inspecting More Than Any Single Weight Matrix
Another line of interpretability works involves inspecting the weight matrices of the model (Li et al. 2016; Dar et al. 2022; Eldan & Lij 2023). Some of the investigations are done locally, neglecting the interplay between different parts of the model. Our result in this section shows that from representational perspective, isolating single weights can also be misleading for interpretability. For this section only, will assume the linear head WHead is identity for simplicity. To consider the effect of pruning, we will also extend the parameterization of LayerNorm module (Equation 7 as
LNC.N (A).,. = PLA.. max{1|P__ (|PP_.,)ll.e)) (1 (1--80 b)A..
which corresponds to a weighted residual branch; note that the original I LayerNorm corresponds to [Nc Let 0 denote the set of parameters of this extended parameterization.
We define the nonstructural pruning as:
Definition& 4 (Nonstructural pruning). Under the extended parameterization, nonstructural pruning of Transformer with parameter @ is a Transformer with the same architecture and parameter 0', so that for any weight matrix W in 0, the corresponding matrix W' in 0' has W E (Wa...) 0}, Vi,j-
To measure the quality of the pruning, define the e-approximation:
Definition 5 (--approximation) Given two meiric spaces A, B with the same metric || I|, function f: A + B is an e-approximation of function g with respect to that metric, if and only if.
Vx E A, [f())) g(x))l S c||==||-
The metric, unless otherwise specified, will be the 2-norm for vectors and the 2-norm for matrices: Definition 6. The 1, 2-norm of a matrix A is the max row norm, i.e. ||A||,, = max ||A.iil2:
With these definitions, we are ready state the main result of this section:
Theorem 2 (Indistinguishability From Single Component). Consider any L-layer Transformer T (Equation (1O) with embedding dimension m, attention dimension mas and finncttoo as layer ReLU MLP with width w. For any d E (0, 1) and N E N+ consider AL-layer random Transformer Trange with embedding dimension Maaag = O(m log( Lm/ ( attention dimension Marge.a Omma log m.mLN, ), and projection function giarge as 4-layer ReLU MLP with width Wlarge (max (m, w) Log wmL.N)
*This verified empirically: uniform-attention models have attention weights fix 0 and are to fit the distribution almost perfectly (> 99% accuracy).
$ 'Here the starting token is necessary because otherwise, the Transformer with uniform attention will have the same outputs for prefix p and prefix @ p. which @ denotes concatenation, iee. p $ p means the same string p repeated twice.
'This is opposed to structural pruning, which prunes entire rows/columns of weight matrices.
7

---

Assume that || & 1 for every weight matrix W in T, and suppose the weights are randomly sampled as Wi, U(-1,1) 1) for every W E Turge Then, with probability à over the randomness of Turree. there exists a nonstructural pruning (Definition 4) of Thurge. denoted as Thage which c-
approximates T with respect to 1 any input X E R R satisfying
X |1,22 S
Proof sketch: connection to Lottery Tickets. Theorem can be interpreted as a lottery ticket
hypothesis (Frankle & Carbin 2018 Malach et al. 2020) for randomly initialized Transformers, which can of independent interest. The proof repeatedly uses an extension of Theorem I of Pensia al. (2020), where it 1) first prunes the (2/ 1) and 2/-th layers of Thrge to approximate T for each / E [4] (Lemmaa 6). and 2) then prunes the remaining 2L + to 4L-th layers of Tharge to approximate the identity function. The full proof is deferred to Appendix C.5
Noting that the layers used to approximate the identity can appear at arbitrary depth in Thages a direct corollary of Theorem iite is that one cannot distinguish between two functionally different Transformers by inspecting any single weight matrix only:
Corollary 2. Let T1, To and Thane follow the same definition and assumptions as 'T and Taagee in The- orem 2 Pick any weight matrix W in Thorze. then with probability 1 6 over the randomness of Tiorze- there exist two Transformers 1, Torre 2 pruned from Tirge. such that Taane e-approximate To Vi [1, and TLage, b, Torre. 2 coincide on the pruned versions of W.
Hence, one should be cautious when using methods based solely on individual components to interpret the overall function of a Transformer.
Experiments
Our theory in Section 3 proves the existence of abundant non-stack-like attention patterns, all of which suffice for (near-Joptimal generalization on Dyck. However, could it be that stack-like solutions are more frequently discovered empirically, due to potential implicit biases in the architecture and the training procedure? In this section, we show there is no evidence for such implicit bias in standard training (Section 4.1). Additionally, we propose a regularization term based on the balance condition (Theorem which leads to better length generalization (Section 4.2)
4.1 Different Attention Patterns Can Be Learned To Generate Dyek
We empirically verify theoretical findings that Dyck solutions can give rise to variety of attention patterns, by evaluating the accuracy of predicting the last bracket of a prefix (Equation (2) given the rest of the prefix. We only consider prefixes ending with closing bracket, so that there exists unique correct closing bracket which a correct parser should be able to determine. The experiments in this section are based Transformers with 2 layers and head, hidden dimension 50 and embedding dimension 50, trained using Adam. Additional results for three-layer Transformers are provided in Appendix D.3 The training data consists of valid Dyck2, sequences of length less than 28 generated with q 0.5. When tested in-distribution, all models are able achieve 97% accuracy.
Variation in attention patterns First, as a response to (Q1), we observe that attention patterns of Transformers trained on Dyck are not always stack-like (Figure []. In fact, the attention patterns differ even across different random initialization. Moreover, while ( that position encoding is not necessary for a Transformer to generate Dyck, 8 adding the position encoding ? does affect the attention patterns (Figures Icland Idh.
7 Herr the input and output dimension of Turge is actually Masgg which is larger than m; additional dimensions are padded with zeroes. The norm constraint can be easily extended to an arbitrary constant.
'This verified empirically, as Transformers with no positional encoding achieve > 97% accuracy.
WW use the linear positional encoding following Yao et al. 2021 : for the is. position, the encoding is detined to be (i) == i/Tmax for some T Tmax-
8

---

5
(a) Embedding
run
(b) Embedding
15 run
(c) Embedding
(d) Embedding 16
Figure 2: Second-layer attention patterns of two-layer Transformers with minimal first layer: (a), (b) are based on embedding I3 with different learning rates, where the attention patterns show much variance Theorem [ predicts. (c), (d) based on embedding 17 and [6 Different embedding functions lead to diverse attention patterns, most of which are not stack-like.
Figure 3: Relationship Between Balance Violation and Length Generalization. Ac- curacy from Transformers with minimal first layer with embedding [5] using both stan- dard training and contrastive regularization (Equation (8)). Standard training leas to high balance violations which negatively relate with length generalization performance. Contrastive regularization helps reduce the balance violation and improve the length gen- eralization performance.
1.6
Contrastive Default Training
Balance Violation
1.4
1.2
1.0
0.8
0.6
0.4
0.2
0.825
0.850
0.875
0.900
0.925
0.950
0.975
1.000
Length Generalization Acc
Specifically, for 2-layer Transformers with a minimal first layer, we experiment with three different types embeddings e: let o, denote the one-hot embedding where o,
e(Tr.a) 01t-1)++d 222D
(15)
e(Tr.)) o Oa E R 2R+D
(16)
el e(Tr..) o @ ccos (0.) sin (0a) E 22 02 arctan (
(17)
where + denotes vector concatenation. Equation 15 is the standard one-hot embedding for Tr.a Equation (16) is the concatenation of one-hot embedding of types and depths. Finally, Equation {17) is the embedding constructed in Yao et al. 2021). As shown in Figure the attention patterns learned by Transformers exhibit large variance between different choices of architectures and learning rates, and most learned attention patterns are not stack-like.
Quantifying the variation random initializations. We define the attention variation between two attention patterns A1, A2 as Variation (A1, A2) || ?2 for A1, Ag IR. N over an length-N input sequence. We report the average attention variation of each architecture based on random initializations.
We now quantify the variation in attention by comparing across multiple
10 we observe that for standard two layer training, the average attention variation is 2.20 with linear position embedding. and is 2.27 without position embedding. Both numbers are close to the random baseline value 2.85 [1] showing that the attention head learned by different initializations indeed tend to be very different. We also experiment with Transformer with minimal first layer and the embedding in Equation (15), where the average variation is reduced to 0.24. We hypothesize that the structural constraints in this setting provide sufficiently strong inductive bias that limit the variation.
On the prefix (ΑΑЛ))((())
Thiss prefix contains brackets of all types and depths. Results with different prefixes provided in Ap- pendix D33 The random baseline is calculated by generating purely random attention patterns (from the simplex. i.e. random square matrices s.t. each row sums up and calculate the average attention variation between them.

---

4.2 Guiding The Transformer To Learn Balanced Attention
In our experiments, we observe that although models learned via standard training that can generalize well in distribution, the length generalization performance is far from optimal. This implies that the models do not correctly identify the parsing algorithm for Dyck when learning from finite samples. natural question is: can we guide Transformers towards correct algorithms, as evidenced by improved generalization performance on longer Dyck sequences?
In the following, we measure length generalization performance by the model accuracy on valid Dyck prefixes with length randomly sampled from 400 500, which corresponds around 16 times the length of the training sequences, Inspired by results in Section 3 we propose regularization term to encourage more balanced attentions, which leads better length generalization.
Regularizing for balance violation improves length generalization accuracy We denote the balance violation of a Transformer as 3 == B.,,d i.j [Sd.d" ".g'",,.'/'' Pa.jl for S, P defined in Equations (31) and 33) Theorem predicts that for models with minimal first layer, perfect length generalization design contrastive training objective to reduce the balance violation, which ideally would lead to improved length generalization. Specifically, let pr denote prefix of nested pairs of brackets of for ([D)), and let T(s Pr denote the logits for s when T takes as input the concatenation of pr and s. We define the contrastive regularization term Reontrasivve (s) as the mean squared error between the logits of (s) and ((s pr s), taking expectation over r and p,:
requires 3 to be zero. Inspired by this observation,
E (DD...
[I| +) - [())
(18)
Following the same intuition as in the proof of Theorem | then the contrastive loss will be zero. Models trained with contrastive loss show reduced balance violation as well as improved length generalization performance, as shown in Figure
if the model can perfectly
Conclusion
Why interpreting individual components sometimes leads misconceptions? Through case study of the Dyck grammar, we provide theoretical and empirical evidence that even in this simple and well-understood setup, Transformers can implement a rich set of non-interpretable solutions. This reflected both by diverse attention patterns and by the absence of musk-specific structures in local components. Our results directly imply similar conclusions for more complex Transformer models; see Appendix C. for technical details. Together, this work provides definite proof that myopic interpretabilityy. L.e. methods based examining individual components only, are not sufficient for understanding the functionality of a trained Transformer.
Our results do not preclude that interpretable attention patterns can emerge; however, they do suggest that interpretable patterns can be infrequent. We discuss the implications for multi-head, overparameterized Transformers trained on more complex data distributions in Appendix B Moreover, our current results pertain to the existence of solutions; an interesting next step is to study how "inductive biases" given by the synergy of the optimization algorithm and the architecture affect the solutions found.
Acknowledgement
This work was in part supported by NSF awards IIS-2211907, CCF-2238523, and Amazon Research Award.
References
Yonatan Belinkov. Probing classifiers: Promises, shortcomings, and advances. Computational Linguis- fics, 48(1)22072219 March 2022. doi: 10.1162/coli_a_000 Lacelii__0000 URL https::/acclatthooogg 2tgg/2222cc111
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the Ability and Limitations of Trans- formers to Recognize Formal Languages. In Proceedings of the 2020 Conference on Empir- ical Methods in Natural Language Processing (EMNLP), pp. 7096-7116, Online, November
10

---

Nick Cammarata, Shan Carter, Gabriel Goh, Chris Olah, Michael Petrov, Ludwig Schubert, Chelsea Voss, Ben Egan, and Swee Kiat Lim. Thread: Circuits. Distill, 2020. doi: 1 5/distill.00024. https://disilllpub/200occcci 2020a. Association for Computational Linguistics. doi: 10.1865511122200mmmmmmmmmim URL ittps://aclanthology .rg. wrg//020. mammlp-mmin.555
Satwik Bhattamishra, Arkil Patel, and Navin Goyal. On the computational power of trans- formers and its implications in sequence modeling. In Proceedings of the 24th Conference on Computational Natural Language Learning, pp. 455-475, Online, November 2020b. As- sociation for Computational Linguistics. doi: N0.18653/1/2022.comm //aclanthology.ooo www.ellooooooooo/o/ooooooo 2020. http:/222.0cco..... conll-1.37
URL https
Tolga Bolukbasi, Adam Pearce, Ann Yuan, Andy Coenen, Emily Reif, Fernanda Viégas, and Martin Wattenberg. An interpretability illusion for bert. arXiv preprint arXiv: 10tp-2104.071443 2021.
Gino Brunner, Yang Liu, Damian Pascual, Oliver Richter, Massimiliano Ciaramita, and Roger Watten- hofer. On identifiability in transformers. In International Conference on Learning Representations, 2020.
B. Chughtai, Lawrence Chan, and Neel Nanda. A toy model of universality: Reverse engineering how networks learn group operations. International Conference on Machine Learning, 2023, doi: 1.48550/a2Xiv.2302.33000
Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D. Manning. What does BERT look at? an analysis of BERT's attention. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 276-286, Florence, Italy, August 2019. Association for Computational Linguistics. doi: 10.18653/v1/W19-48222 URL https //aclanthology .rg.gy..rggo.. wrg//19- 2tg/WW9-4822
Guy Dar, Mor Geva, Ankit Gupta, and Jonathan Berant. Analyzing transformers in embedding space, 2022.
Yichuan Deng, Zhihang Li, and Zhao Song. Attention scheme inspired softmax regression, 2023.
Javid Ebrahimi, Dhruv Gelda, and Wei Zhang. How can self-attention networks recognize Dyck-n languages? In Findings of the Association for Computational Linguistics: EMNLP 2020, pp. 4301-4306, Online, November 2020. Association for Computational Linguistics. doi: 10. 10.18v53/v1/ JtRps
Sindings-emnlp.36.
. org/ 2020. findings-emmnnn emmlp... 384
Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. Inductive biases and variable creation in self-attention mechanisms. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 5793-58311 PMLR, 17-23 Jul 2022. URL
mlr wwppprrsvv1221 wwwp:////eeeeeee 1man22222.....mmmmmmmm html
Ronen Eldan and Yuanzhi Li. Tinystories: How small can language models be and still speak coherent english?, 2023.
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 HatfieldDDodss, Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. A mathematical framework for transformer circuits. Transformer Circuits Thread, 2021. http:://rransfomee-ciicuittt,pp
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. arXiv preprint arXiv:2010.01412. 2020.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. International Conference On Learning Representations, 2018.
Yeqi Gao, Sridhar Mahadevan, and Zhao Song. An over-parameterized exponential regression, 2023,

---

F. Gers and J. Schmidhuber. Lstm recurrent networks learn simple context-free and context-sensitive languages. IEEE transactions on neural networks, 12 6:1333-40, 2001.
Christopher Grimsley, Elijah Mayfield, and Julia R.S. Bursten. Why attention is not explana- tion: Surgical intervention and causal reasoning about neural models. In Proceedings of the Twelfth Language Resources and Evaluation Conference, pp. 1780-1790, Marseille, France, May 2020. European Language Resources Association. ISBN 979-10-95546-34-4. URL https://aclante
org 2020. 1rec- 1.220
Jonathan Haab, Nicolas Deutschmann, and María Rodríguez Martínez. Is attention interpretation? quantitative assessment on sets. In Machine Learning and Principles and Practice of Knowledge Discovery in Databases, pp. 303-321, Cham, 2023. Springer Nature Switzerland. ISBN 978-3-
031-23618-1.
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Trans. Assoc. Comput, Linguistics, 8:156-171, 2020. doi: 10. (0.1162/aacl_a) al_00306. httpps:tp:///do org/ 10. 11w2/11aaaaa 2a/22/tac__55 a_ 00306
John Hewitt and Percy Liang. Designing and interpreting probes with control tasks. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNEL pp. 2733- 2743, Hong Kong, China, November 2019. Association for Computational Linguisties. doi: 10. N0.18653/v1/DD1-12755 URL ott.
http:///aaaaattoogy.ooooo orw.e//-.r////11100000
John Hewitt and Christopher D Manning. A structural probe for finding syntax in word representations. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers),
pp. 4129 4138, 2019.
John Hewitt, Michael Hahn, Surya Ganguli, Percy Liang, and Christopher D Manning. Rnns can generate bounded hierarchical languages with optimal memory. arXiv preprint arXiv:2010.07515, 2020.
Phu Mon Htut, Jason Phang, Shikha Bordia, and Samuel R. Bowman. Do attention heads in bert track syntactic dependencies?, 2019.
Sarthak Jain and Byron C. Wallace. Attention is not Explanation. In Proceedings the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 3543-3553 33566, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 2..18653/v1/N19 1357.
URL https::/ Barellloyy.orgg//.. www.oogg............. Dtgg/N19-338 1357
Samy Jelassi, Michael Eli Sander, and Yuanzhi Li. Vision transformers provably learn spatial structure. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL eMW9AkXaREI
nwt net/forumiid-
Lifeng Jin, Finale Doshi-Velez, Timothy Miller, William Schuler, and Lane Schwartz. Unsupervised grammar induction with depth-bounded pefg. Transactions of the Association for Computational Linguistics, 6:21 1-224, 2018
Fred Karlsson. Constraints multiple center-embedding of clauses. Journal of Linguistics, 43(2): 365-392, 2007.
Goro Kobayashi, Tatsuki Kuribayashi, Sho Yokoi, and Kentaro Inui. Attention is not only weight:
Analyzing transformers with vector norms. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 7057-7075, Online, November 2020. Association for Computational Linguistics. doi: 10.18653/w1/2222.0oom org/2020. /aaclanthology org/ 2020 emnlp-main.55 574
574. URL https
Olga Kovaleva, Alexey Romanov, Anna Rogers, and Anna Rumshisky. Revealing the dark secrets of BERT. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language
12

---

Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP. IJCNLP). pp. 3365-4374, Hong Kong, China, November 2019. Association for Computational Linguistics. doi: 10. 10.1863/11/DD1-1144 1445. URL
htt.a//mtnooooooooo///9-9-- 1445
Jiwei Li, Xinlei Chen, Eduard Hovy, and Dan Jurafsky. Visualizing and understanding neural models in NLP. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pp. 681-691, San Diego, California, June 2016. Association for Computational Linguistics. doi: 10.18653/v1/ N16-1082. URL hatttps://acllantooooggg...
-082
Xian and Hongyu Gong. Robust optimization for multilingual translation with imbalanced data. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (ods.), Advances in Neural Information Processing Systems, volume 34, pp. 25086-25099, Cur- ran Associates, Inc., 2021. URL https: https://proceeddii http:///oooeeeen...o/ www.gg...uips..om ceeurips.cccpapeeeeee pwwppppppp/p/aaa//p 352400cc2281177964444446666666.3
Paper. pdf
Yuchen Li and Andrej Risteski. The limitations of limited context for constituency parsing. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 2675-667666 2687, Online, August 2021. Association for Computational Linguistics. doi: 10.18653/v1/2021 wtw.://////.....oonoo..a.. aal--ccng2008 URL http:////laaaatolggoooo org/ 2021/2011.00 2
208
Yuchen Li, Yuanzhi Li, and Andrej Risteski. How do transformers learn topic structure: Towards a mechanistic understanding. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 19689-19729. PMLR, 23-29 Jul 2023. URL https: htttp:://proceedingss mlr. presa/v202/ 1123p. 11mlp.html
Yongjie Lin, Yi Chern Tan, and Robert Frank. Open sesame: Getting inside BERT's s linguistic knowl- edge. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 241-253. Florence, Italy, August 2019. Association for Computational Linguistics. doi: 11118663/1//111110
URL /ttL:tttt///acaatttoo wtt.oaaooooooooo/o///o... org/W19 4825
Bingbin Liu, Daniel Hsu. Pradeep Kumar Ravikumar, and Andrej Risteski. Masked prediction: A parameter identifiability view. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022a. URL httpeviwwwnneeefeeeeeee htte///orummi---Blbbbbb.......e
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In The Eleventh International Conference on Learning Representations, 2023. URL /ttps::t:////
Hong Liu, Sang Michael Xie, Zhiyuan Li, and Tengyu Ma. Same pre-training loss, better downstream: Implicit bias matters for language models. arXiv preprint arXiv:2210. 14199, 2022b.
Liyunn Liu, Xiaodong Liu, Jianfeng Gao, Weizhu Chen, and Jiawei Han. Understanding the
difficulty of training transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 5747-5763, Online, November 2020. Association for Computational Linguisties. doi: 10. 102.:3301/2200..mmll...m
URL
https://aclantae
orgg20200 emmlp-main www.mmiiin....... 463
Nelson F. Liu, Matt Gardner, Yonatan Belinkov, Matthew E. Peters, and Noah A. Smith. Linguistic knowledge and transferability of contextual representations. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pp. 1073-1094, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 11885//1//N19-111222 URL https www.aathhooooooooo1199----1
Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In International Conference on Machine Learning, pp- 6682-6691 PMLR, 2020.
13

---

Clara Meister, Stefan Lazov, Isabelle Augenstein, and Ryan Cotterell. Is sparse attention more interpretable? In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the I 11th International Join Conference on Natural Language Processing (Volume 2: Short Papers), pp. 122-129, Online, August 2021. Association for Computational Linguisties. doi: 10.18653/v1/2022 acl-sshor.....t.............. 17. URLhttps: http:p::/aaaaantthlaaaa
2021 acl-sshrtt.... 17
William Merrill. Sequential neural networks as automata. In Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges, pp. 1-13, Florence, August 2019. Association for Computational Linguistics. doi: 10. 10.18853/v1/W11
URL httpp://www aclweb. org/
anthology/W19 3901
Paul Michel, Omer Levy, and Graham Neubig. Are sixteen heads really better than one? In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, cwt.rrips.ccpppppeeaaee wwwpccppppe..ee files/ pappppppp/////ilee pdf
Inc., 2019. URL 2x60aaabc22111c32222200c65555252
Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt, Progress measures for grokking via mechanistic interpretability. In The Eleventh International Conference on Learning Representations, 2023. Utthhttps:://// //ppnrevii//. www.:/eet/ffror Xd-.rrXn
Toan Q. Nguyen and Julian Salazar. Transformers without tears: Improving the normalization of self-attention. In Proceedings of the 16th International Conference on Spoken Language Translation, Hong Kong, November 2-3 2019. Association for Computational Linguistics. URL https://aclatthology) org wttp:///21..wwsst--1111 iwslt-
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Scott Johnston, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. In-context learning and induction heads. Transformer Circuits Thread, 2022. html.
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Optimal lottery tickets via subset sum: Logarithmic over-parameterization sufficient. Advances in neural information processing systems, 33:2599- 22110 2020.
Jorge Perez, Pablo Barcelo, and Javier Marinkovic. Attention is turing-complete. Journal of Machine Learning Research, 22(75):1 -351, 2021. http::t::// http://rrrrrg/pppp//////////000/
html
Sai Prasanna, Anna Rogers, and Anna Rumshisky. When BERT Plays the Lottery, All Tickets Are Winning. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 5208-3229, Online, November 2020. Association for Computational Linguistics. doi: 10.18653/112222.emmmppp 255. 259. URL httpp:://accaaaooooog..oo///////
Smnlp-main.22 .59
Alessandro Raganato and Jörg Tiedemann. An analysis of encoder representations in transformer- based machine translation. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: An- alyzing and Interpreting Neural Networks for NLP, pp. 287-297, Brussels, Belgium, Novem- ber 2018. Association for Computational Linguisties. doi: 10.18653/11/W18-544 URL
htttps///aclanthologg wwt.//o-g////// 5431
Anna Rogers, Olga Kovaleva, and Anna Rumshisky. A primer in bertology: What we know about how bert works. Transactions of the Association for Computational Linguisties, 8:842-866 8666, 2020.
M.P. Schützenberger. On context- free languages and push-down automata. Information and Control, URL
6(3):246-264, 1963. ISSN 0019-9958. doi: httpss///ww.siiimciirreett http://ccrrrett.ccoccccceeeeeeee httpa///tw.....ee.../..e.eeaatta
Soña Serrano and Noah A. Smith. attention interpretable? In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 2931-2951, Florence, Italy, July 2019, Association for Computational Linguistics. doi: 10. 18653/v1//11-11882 URL httpps
//aclanthology. .rweloggy.o.o//// wwtp///-///P/000
14

---

Hava T. Siegelmann and Eduardo D. Sontag. On the computational power of neural nets. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT '92, pp. 440-449, New York, NY, USA, 1992. Association for Computing Machinery. ISBN 089791497X. doi: 10.1145/1
/ 1145/ 2et55//3135...0 130432
Kaiser Sun and Ana Marasović. Effective attention sheds light on interpretability. In Findings of the Association for Computational Linguisties: ACL-IJCNLP 2021, pp. 4126-4135, Online, August 2021. Association for Computational Linguistics, doi: 10.11863/11/200 http://...22.2..nn-eeeeee. findings--acl.61. URL
ittps://aclanthologgy wtt.:/oorrr/22...nnnngeeeee findingn-acll.i.. ac1
Mirac Suzgun, Yonatan Belinkov, Stuart Shieber, and Sebastian Gehrmann. LSTM networks can per- form dynamic counting. In Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges, pp. 44-54, Florence, August 2019. Association for Computational Linguistics. doi: 10.18653/v1/W 19-3905. URL http:://p//// hwwp://///wwww.//// aclweb. org/ aath//oog///lss WW19-3905
Ian Tenney, Dipanjan Das, and Ellie Pavlick. Bert rediscovers the classical nlp pipeline. arXiv preprint ar
2019.
Jesse Vig and Yonatan Belinkov. Analyzing the structure of attention transformer language model. In Proceedings of the 2019 ACI. Workshop BlackboxNI.P: Analyzing and Interpreting Neural Networks for NLP. pp. 63-76, Florence, Italy, August 2019. Association for Computational Linguisties. doi: 10. N0.11666/11//119446
URL
Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned. In Proceedings of the 57th Anmual Meeting of the Association for Computational Linguistics, pp. 5797-5808, Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10. 10.18653/ 1580. URL
Ptg/ -19- 1580
Kevin Ro Wang, Alexandre Variengien, Arthur Conmy, Buck Shlegeris, and Jacob Steinhardt. Inter- pretability in the wild: a circuit for indirect object identification in GPT-2 small. In International Conference on Learning Representations, 2023. URL TtLhhttp::// httpttttts//perreatiiae www.teeuutiiiii.
NpsVSS6o4ul
Colin Wei, Yining Chen, and Tengyu Ma. Statistically meaningful approxiaaion:::::: a case study on approximating turing machines with transformers, 2021. URL https://arxiv..rr /bs///1/// 13163
Gail Weiss, Yoav Goldberg, and Eran Yahav. On the practical computational power of finite precision mns for language recognition. arXiv preprint 1eX.vv:805.044 2018
Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11080-11000 1090, PMLR, 18-24 Jul 2021. URL https://procceednggs mlr.
html
Sarah Wiegreffe and Yuval Pinter. Attention is not not explanation. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 11-20, Hong Kong, China, November 2019. Association for Computational Linguisties. doi: 10.19655/ URL wttp
Zhiyong Wu, Yun Chen, Ben Kao, and Qun Liu. Perturbed masking: Parameter-free free probing for analyzing and interpreting BERT. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 1166641766 Online, July 2020. Association for Computational Linguistics. doi: 10.18653/w1/2020. acl mel.mai...38.. URL httpp::/aacaanthologg
acl mai-main.cc 383
Ruibin Xiong, Yunchang Yang, Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tie- Yan Liu. On layer normalization in the transformer architecture. In Proceedings of the 37th International Conference on Machine Learning, ICMI:20. JMI..org,
2020.
15

---

Shunyu Yao, Binghui Peng, Christos Papadimitriou, and Karthik Narasimhan. Self-attention networks can process bounded hierarchical languages. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 1 1ith International Joint Conference on Natural Language Processing (Volume I: Long Papers), pp. 3770-3785, Online, August 2021. Association for Computational Linguistics. doi: 10.18653/v wttp:///1221111111ll/0 www.-lllng.29999 URL https //aclanthology. org/ 222//22111.2 acl2.accl-- lon...n...... 292
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are trans- formers universal approximators of sequenseeto-seequeeee functions? In International Conference on Learning Representations, 2020. URL. http:tttpp://opeeee.eeer net -ererdddBBBay BddBBxy
Marvin Zhang, Henrik Marklund, Abhishek Gupta, Sergey Levine, and Chelsea Finn. Adaptive risk minimization: meta-learning approach for tackling group shift. arXiv preprini ar arXiv:2007.0293: 2020.
Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, and Tal Wagner. Unveiling transformers with lego: synthetic reasoning task, 2022. httpss///aaxx org/ abs/2206.0433
Haoyu Zhao, Abhishek Panigrahi, Rong Ge, and Sanjeev Arora. Do transformers parse while predicting the masked word?, 2023.
Ziqian Zhong, Ziming Liu, Max Tegmark, and Jacob Andreas. The clock and the pizza: Two stories in mechanistic explanation of neural networks. arXiv preprint arXiv: 2306.17844 2023.
16

---

Contents
Introduction
1.1
Related Work
2
Problem Setup
3
Theoretical Analyses
3.1
Interpretability Requires Inspecting More Than Attention Patterns
3.1.1
Perfect Balance Condition: Ideal Generalization of Unbounded Length
3.2
Interpretability Requires Inspecting More Than Any Single Weight Matrix
4
Experiments
Different Attention Patterns Can Be Learned To Generate Dyck
4.2
Guiding The Transformer To Learn Balanced Attention
10
5
Conclusion
10
Additional Related Work
18
Are interpretable attention patterns useful?
20
Can interpretable attention patterns be misleading?
20
B.2 Are attention heads with interpretable patterns more important?
22
Omitted Proofs in Section
23
Proof of Theorem
23
Implication of our results to larger models
26
Proof of Corollary
27
Approximate Balance Condition For Finite Length Training Data
................................
27
C.4.1
Proof of Theorem
29
C.5
Proof of Theorem 2
31
C.5.1 Helper lemmas for Theorem
33
C.6
Technical Lemmas
39
Discussion on Architecture Choices
41
Experiments
42
D.I Training Details
42
D.2 Additional Results on Dyck Prefix
42
D.3 Extended Experiments
43
17

---

A Additional Related Work
Interpreting Transformer solutions
Prior empirical works show that Transformers trained on natural language data can produce representations that contain rich syntactic and semantic information,
by designing a wide range of "probing" tasks (Raganato & Tiedemann 2018 Liu et al. 2019 Hewitt
& Manning 2019 Clark et al.) 2019 Tenney et al. [2019] Hewitt & Liang. 2019 Kovaleva al.
2019]] Lin et al. 2019 Wu et al., 2020, Belinkov 2022) (or other approaches cee using the attention
weights parameters neurons directly Vig & Belinkov 2019 Htut et al. 2019 [Sun & Marasović
2021 Eldan & Li ). However, there is no canonical way to probe the model, partially due to the huge design space of probing tasks, and even a slight change in the setup may lead to very different (sometimes even seemingly contradictory) interpretations of the result (Hewitt & Liang 2019). In this work, we tackle such ambiguity through different perspective- by developing formal (theoretical) understanding of solutions learned by Transformers. Our results imply that it may be challenging to try to interpret Transformer solutions based on individual parameters (Li et al.) [016]] Dar et al.) 2022), or based on constructive proofs (unless the Transformer is specially trained to be aligned with a certain algorithm, as in Weiss et al. 2021).
Interpreting attention patterns Prior works (Jain & Wallace, 2019; Serrano & Smith 2019
Rogers et al., [2020] Grimsley et al. 2020, Brunner et al. [2020] Prasanna et al. 2020 Meister et al. 2021; 2021; Bolukbasi et al. [021]] Haab et al.) 2023] inter alia) present negative results on deriving
explanations from attention weights using approaches by Vig & Belinkov (019);; Kobayashi et al.
(2020) inter alia). However, Wiegreffe & Pinter (2019) argues to the contrary by pointing out flaws in the experimental design and arguments of some of the prior works; they also call for thcoretical analysis on the issue. Hence, a takeaway from these prior works is that expositions on explainability based on attention requires clearly defining the notion of explainability adopted (often task -ask-spec....). In our work, we restrict our main theoretical analysis to the fully defined data distribution of Dyck language (Definition D) and define "interpretable attention pattern" the stack-like pattern proposed in prior theoretical Yao et al. 2021) and empirical (Ebrahimi et al.] (020) works. These concrete settings and definitions allow us to mathematically state our results and provide theoretical reasons.
Theoretical understanding of representability Methodologically,,
work joins long line of prior works that characterize the solution of neural networks via the lens of simple synthetic data, from class results on RNN representability (Siegelmann & Sontag 1992; Gers & Schmidhuber
2001 Weiss et al. 2018 Suzgun et al. 2019 Merrill 2019: Hewitt et al.) 2020). to the more recent
Transformer results parity (Hahn) 2020), Dyck ( (Yao et al.) (021). topic model (Li al. 2023).
and formal grammars in general [Bhattamishra et al. 2020a Li & Risteski, 2021; Zhang et al. 2022
Liu et al. 2023 Zhao et al.) 2023). Our work complements prior works by showing that although representational results can be obtained via intuitive "constructive proofis" that assign values to the weight matrices, the model does not typically converge to those intuitive solutions practice. Similar messages are conveyed in [Lu et al. (2023). which presents different types of constructions using different numbers of layers. In contrast, we show that there exist multiple different constructions even when the number of layers is kept the same.
There are also theoretical results Transformers in terms of Turing completeness (Bhattamishra ett al. 2020b) Perez et al. 202T), universal approximatabillity (Yun et al. 2020). and statistical sample complexity (Wei et al. 2021 Edelman et al. 2022), which are orthogonal to our work.
Transformer optimization Given multiple global optima, understanding Transformer solutions requires analyzing the training dynamics. Recent works theoretically analyze the learning process of Transformers on simple data distributions, e.g. when the attention weights only depend on the position information (Jelassi et al. 2002). or only depend on the content (Li et al. 2023). Our work studies a -ottivated setting in which both content and position are critical. We also highlight that Transformer solutions are very sensitive to detailed changes, such as positional encoding, layer norm, sharpness regularization (Foret et al. 20200), or pre- pre-training task (Liu et al., 2022a). On a related topic but towards different goals, a series of prior works aim to improve the training process of Transformers with algorithmic insights (Nguyen & Salazar 2019 Xiong et al. 2020 Liu et al.
2020 Zhang et al.) 2020 Li & Gong 2021 inter alia). An end-to-end theoretical characterization of the training dynamics remains an open problem; recent works that propose useful techniques towards
this goal include Gao et al. 2023 Dong et al. 2023
18

---

Mechanistic interpretability Finally, it is worth noting that the challenges highlighted in our work do contradict the line of prior works that aim improve mechanistic interpretability into trained
model the training process (Cammarata et al., 2020 Elhage et al. 2021 Olsson et al. 2022 Nanda
jtt al. 2023 Chughtai al. 2023 Li et al. [023) Wang al. 2023 Zhong et al., 2023): although we prove that components (e-g. attention scores) of trained Transformers do not generally admit intuitive interpretations based on the data distribution, it is still possible to develop circuit-leve understanding
about particular model, measures that closely track the training process, following these prior works.
19

---

B Are interpretable attention patterns useful?
Our results Section and Section 4.1 demonstrate that Transformers are sufficiently expressive that (near-)optimal loss on Dyck languages can be achieved by variety of attention patterns, many of which may not be interpretable.
However, multiple prior works have shown that for multi-layer multi-head Transformers trained on natural language datasets, often possible locate attention heads that produce interpretable attention patterns (Vig & Belinkov 2019)] Htut et al., 2019 Sun & Marasović (021). ). Hence, is also illustrative consider the "converse question' " of (QT): when attention heads do learn to produce attention patterns that suggest intuitive interpretations, what benefits can they bring?
We discuss this through two perspectives:
Reliability of interpretation: the Transformer necessarily implementing a solution consistent with such interpretation based on the attention patterns? (Section [.1)
Usefulness for task performance: Are those interpretable attention heads more important for the task than other uninterpretable attention heads? (Section B.2)
We present preliminary analysis these questions, and motivate future works the interpretability of attention patterns using rigorous theoretical analysis and carefully designed experiments.
B.1 Can interpretable attention patterns misleading?
We show through simple argument that interpretations based attention patterns can sometimes be misleading. as we formalize the following proposition:
Proposition 1. Consider L-layer Transformer T (Equation (TO). For any W w Xm (I E [L), there exist Head E 222xx and bHead 122h such that T(Z) = 0, AZ.
While its proof is trivial (simply setting WHeadd 0 and bHead 0 suffices), Proposition 1 imppies that the solution represented by the Transformer could possibly be independent of the attention patterns in all the layers (1 through l). Hence, it could be misleading interpret Transformer solutions solely based on these attention patterns.
Empirically, Transformers trained on Dyck indeed sometimes produce misleading attention patterns.
We present one representative example in Figure and Figure in which all interpretable attention patterns are misleading.
We also present additional results in Figure in which some interpretable atlention patterns are misleading, and some are not.
Figure 4: Even interpretable attention patterns can be misleading: For 4-layer Transformer trained on Dyck with the copying task (with > 96% validation accuracy), i.c. the output should be exactly the same as the input, the attention patterns in some layers seem interpretable: (layer 2) attending bracket type a) (b; (layer 3) attending closing bracketss; (layer 4) neve attending to bracket type a); However, none of them are informative of the copying task. This is possible because Transformers
the residual connections (or weights MIPP the value matrices) solve copying, bypassing the need of using attention.
Similar message has been conveyed prior works Bolukbasi et al. (202)) and future works may aim to achieve the faithfulness, completeness, and minimality conditions in Wang et al. (2023).
20

---

layeeO
START lb (b bi ja (a (b a) a) la a) b) (a a)
8-
4-
8-
START
01 01
Figure 5: Even interpretable attention patterns can be misleading: For a I-layer Transformer trained on Dyck with the copying task (with > 90% validation accuracy), i.e. the output should be exactly the same as the input, the attention pattern seems to be attending to closing brackets only, but that is not informative of the copying task.
layer o
(b) layer of
Figure 6: Even interpretable attention patterns can be misleading: For a 4-layer Transformer trained on Dyck with the copying task (with > 96% validation accuracy), i.e. the output should be exactly the same as the input, both types of attention patterns are common: (a) attending to closing bracketss, which is uninformative of the copying task; (b) attending to the current position, which solves the copying task.
21

---

B.2 Are attention heads with interpretable patterns more important?
Kovaleva al. 2019) observes that, when the "importance" of attention head is defined as the performance drop the model suffers when the head is disabled, then for most tasks they test, the most important attention head in each layer does not tend be interpretable.
However, experiments by Voita et al. (2019) led to a seemingly contradictory observation: when at- tention heads are systematically pruned by finetuning the Transformer with relaxation of Le-penalty (i.e. encouraging the number of remaining attention heads to be small), most remaining attention heads that survive the pruning can be associated with certain functionalities such positional, syntactic, or attending to rare tokens.
These works seem to bring mixed conclusions to our question: interpretable attention heads more important for task than uninterpretable ones? We interpret these results by conjecturing that the definition of "imppotance" (reflected in their experimental design) plays crucial role:
When the importance of attention head is defined treating all other attention heads fixed, motivating experiments that prune/disable certain heads while keeping other heads unchanged (Michel et al. 2019 Kovaleva et al.) 2019), the conclusion may be mostly pessimistic: mostly strong connection between interpretability and importance.
On the other hand, when the importance of an attention head is defined allowing all other attention heads to adapt to its change, motivating experiments that jointly optimize all attention heads while penalizing the number of heads (Voita et al. 2019), the conclusion may be more optimistic: the heads obtained result of this optimization tend to be interpretable.
We think the following trade-offs apply:
On one hand, the latter setting is more practical, since Transformers typically not trained explicitly ensure that the model performs well when a single attention head is individually disabled; rather, it would be more intuitive think of a group of attention heads as jointly representing some transformation, so when one head is disabled, other heads should be fine-tuned to adapt to the change.
On the other hand, when all other heads change much during such fine-tuning, the resulting set of attention heads no longer admit an unambiguous one-to-one map with the original set of (unpruned) attention heads. As result, the interpretability and importance obtained from the set of pruned heads do not necessarily imply those properties of the original heads.
comprehensive study of this question involves multi-head extensions of our theoretical results (Section 3). and carefully-designed experiments that take the above-mentioned trade-offs into consid- eration. We think these directions are interesting future work.
22

---

C Omitted Proofs in Section 3
C.1 Proof of Theorem
The key step is already shown in Section 3 We will restate the proof rigorously here.
Theorem 1 (Perfect Balance). Consider a two-layer Transformer T (Equation (IO)) with minimal first layer (Assumption 7 and CLN scenario, that is, when the first layer embeddings {e(Ti,a) dee (D) (Definition 2 and second layer parameters ((2) satisfy
(Equation (7). Let O denote the optimal prediction
= [e(T, g = arg min L(O: D D.., YN
where the objective is defined Equation Then,
Equation 11 necessary condition of O, if W satisfies P1 W e(Te,a) # Vt E [b) E [D]-
Equation
is a sufficient condition of O if the set of 2k + encodings are linearly independent for any (D), and the projection
(e(T2-1aa) el ((T2ra))ve()) U (e(ts))
function (2) is a 6-layer MLP 12 with O(k2 (?) width.
Proof. We prove the sufficiency of the balanced condition below; the proof for the necessity has been given in Section 3.1
We will denote the dimension of e(Tr,)) as m.
For any i E [k)] d' E (D). by Equation (11 we can assume that there exists dz,a E IR such that for any E [b). E [D], it holds that,
ai,d' & (e (T21-1,0)) e (T21,)'-)) ( e (
(19)
We will first define the possible index sets of Te.d as = {(2t, d) | I [k],0 D
{(2t - d, [A],
D}. and we will define the rank of (t, d) as
r(t, d) # ((t1.dd) d1) t1 tort = t, d1 S d, (t1, d1) EI]
(20)
Then it is clear that r(t, d) is a one-to-one mapping from I to [2:D]. We will then define the collection of all e(Tr.a) E, satisfying that E.,(1,d) e(T.a), 222DD+1 e(ls).
Because e(Tr,a) are linearly independent, for any (i, d) * d') E I. holds that e(Ti,)) ( e(Tr,a)) + 0. Then based Lemma 16 there exists set of orthonormal vectors (bi)ie(m-2) such that for any di, (i,d') E I, holds that
m 2
Σ
byby (e(Ti,)) e(Ts,))) # (e(Ts,a) - e(Ts,ar)
(21)
1 3T 1===
(22)
We will further construct matrix O as
0 (2t,d-11) exp( 01 bbDDd.
(2(1-1 = b.D+dd-
(23)
O 0,2k4+1 = 0.
The layers are by our construction. We will first use 4 layers to convert input the projection function to a triplet indicating the type and depth of the last token and the type of the last unmatched bracket when the last token is a closed bracket. We will then use another 2 layers to predict the next token probability based on the triplet. This construction may be improved.
I "Reaall the definition of in Equation (20). Comparing O (.1 and 0 O.,(2:-1.a)) the idea is that pair of matched brackets are represented by the same direction (i.e. the direction along b.p.a),, just with different norms.
23

---

fort E [k], d E [D].
We then choose w mR such that
w w =
(24)
Such w is guaranteed to exist, because is of full column rank by the linear independence assumption.
Now based on this construction, we will show that the last column of unnormalized attention output (Equation (9)) depends only on the sequence of unmatched brackets when the last token is closed bracket with depth d greater than or equal to
For any valid Dyck prefix p of length n ending with a closed bracket 72j.d satisfying d 2 1, suppose the list of unmatched open brackets p [T2j [22 1, 1222-1122...> T2ja-1,d Then, the remaining tokens in p are pairs of matching brackets. Denote them by 12t,-1,dy> -2tud4-- for l E [K]. Then the input of the second layer of Transformer X, up to permutation
XP = [e(TT),
-1)...., e(T21x 11,x ()...)...(............. ((T2ax.dx -11) 0(12ja-1,) e(ts)). e(()s))
We will focus the last column of the unnormalized attention output
(x in+1
P1
W (2) - ((C- x) (w x))] 1m++
V X
n+1
PL (W X) |0 (w x) ( (w 1imi
Σ
Pi (W (2)
X) exp (IT x)) gn+2
P1 (W X): cxp XW. x) x)nnt1)
(u (u(T2ce 11, 723,4) + u(T2) -1,d T2j.4))
Σ u (2y. T2j.a) (25)
in which the last line is by definition of .(.,)) in Equation 12) For any indices 8, js: j. d, we can simplify the expression for ((T2) 1,s, T2j.a) by observing that
u(T2j.-1.0 T2j,a) = P1 cxp (T(T2)-
T Two (T2jja))
W (T(2).-1..))
by Eq 12
K
Pi exp (e(T2i)-1.)) (W(2) T e (T2j.a)
0 0. -111--111 1.s)
by Eq
24
exp exp
Pi
(e( (W(2) T W (2) e e
by.
by Equation 23
exp (e( (e(T2).-1.)) (w(2)) T w2(2) e e bj. by Equation 22
(26)
Likewise by Equation
12
Equation
24). Equation
Equation 22
u T25.a) exp (e( T (W(2) K
W
(F(s))) exp(a,..)
(27)
Whhen depth d 0. all brackets are matched, the groundtruth next next-token distribution is the prior distribution over the open brackets. Because in Equation (II) di, da > 1. we handle the depth d' = 0 case separately in Case 2 "t is even, d 0" towards the end of this proof. In the following, focus with depth d > 1.
24

---

By Equation 26 and Equation 27.
u( T212 d2 1. F2j.o) u(T2) 1,de T2).a)
exp (e( (e( (w (2) (
W el (FEEEA) bu D+d
exp (e(T22).
(W W e e(T2jaa)) explarn.de Yoe, D4ds
[exp
(e (e( T (W (2) ( W e (TRJ.a))
(T( )w w e e(T2j,a) + de IDi
exp
(28)
in which the last line is because the terms inside [...] cancel each other, because by Equation 19
e (W(2) (w( e (T2j.a) e e( (W (2) KK
(2)
Tw/l e((2ss)) + dexidx
K
Plugging Equation (28 and Equation (26 into Equation 25
22( a2(X;0(3)
1n+1
u r2j, 1,8: T2j.d)
==1
Σ exp (e(Tii-1.s))
T e((ja)(())))))))))))))))))) bj.D+s
(29)
Therefore, )( lies in the span of (bseD+ We will from now on assume (LN(aa(X; ) nn ). bj, D+e) > M for all possible choices of p ending with closed bracket with grammar depth at least for some constant M E (0, 1). Here M exists because
exp (e(125.-1.)) T(w)) T W (((23.a))
(() bj.
0,
V - exp (2e (2e(T2).-1.) (W w e((25,))
for all possible combination of je, k E [d] and s, and there are only finite number of such combina- tions.
Constructing the projection function g(2) We will finally show there exists 6-layer MLP g(2) with width O (DD2k²) () such that for any dyck prefix q with n being the length q. X being the input of the second layer given and P(()) being the groundtruth next-token probability vector given q it holds that, g (2) (LN(āz(X: ((2))
X,,+1) = P(g).
We will assume the last token of q is Te,d- Suppose that 1m-1, bm is orthonormal basis of the normal space of span (bi,.,, .., bm- then we can first observe that for U b + -m- b holds that
((LN( ((2) ):a+1)) + X. Ue(Tr,))
is unique for every t, d. Then based on Lemma 15, there exists 2-layer MLP with width 4k:D that ((2)).,+1)
maps U (LL((az(X. ((2)) )++1) + X m )) to (1, d). This implies that there exists 2-layer MLP with width 4kD that maps LN (Nz((z(() X; (2))) ).,.)) + X.,. to (t,
Further, let matrix U' = Ej b, where oj the Dk dimension one-hot vector with the j-th entries being 1. Then when is an even number and d 1, based Equation (29 and the definition of M,
O,
T2r- 1,, is not unmatched open brackets in p.
U (L\N( (() (.n11) X
M,
1,0" is an unmatched open brackets in
15 P(g). [he token of has type
25

---

Then based on Lemma 18 there exists 2-layer MLP with width kD that operates on (U" (LNN(ax(X;;0)) )=n++))+++++)))) + X (,m++)) ME|h] for fixed d' and output the nonzero index in it, if such index exists. Hence, we can choose the weight of the first and second layer of g(²), such that the output of the second layer is (t, d) æ, where 2x, is the type of the unmatched open brackets with grammar depth d' if is an even number, d 2 d' 2 1.
Now based on Lemma 17 we can choose the third and fourth layer of g. (2) to perform indexing and let the output of the fourth layer be (4, d, y). where y= Za when d > 1. contains all the necessary information to infer P(q) because it uniquely determines the type of last unmatched open bracket,
16 Notice that this triplet
1. If t odd (i.e. the last bracket is open), and then the type of last unmatched open bracket is t.
2. t is even and = 0, then all the brackets is matched.
/ even and 2 1, then the type of last unmatched bracket is y.
One may finally construct 2-layer MLP f that maps (t, d, y) to the corresponding probability vector. As the input of g has bounded norm,
(())
x S + max ||e(Tr,))))
the output of the constructed 4 layers also has a bounded norm, Hence, we can assume there exists constant M' 1, such that y S M'. Now will discuss by the value of
1. t odd, then one can neglect the third dimension and the correct probability is determined by d and can be represented by width-2D network based Lemma 15
2. J. is even. When d 0, one construct a width-1 network mapping any y to the correct proba- bility distribution as it is unique. When d 2 1, one can construct a width-2K network mapping Fa E [K] the correct probability distribution based on Lemma [5 Then by Lemma 19 one can construct a width-4K D network that maps (d, y) to the corresponding probability distribution.
Putting together and using Lemma 19 again, one can construct width-8K network that maps (f, d, y) to the correct next token probability prediction. The proof is then completed.
C.2 Implication of our results to larger models
Recall that the main conclusion of our paper is that interpretability based on a single Transformer component (e.g. attention pattern
MLP block) can be unreliable, since the set of optimal solutions can give rise to a large set of attention patterns and pruned MI.P weights. Section 3 has demonstrated this with simple two-layer Transformers. The simplicity of this architecture choice is intentional, since our theory on two-layer Transformers directly implies similar conclusions for larger models, as we discuss in this section.
Intuitively, when moving to more complex architectures, the set of solutions can only grow and complicate interpretability further, hence main conclusion still stands. For example, even though Theorem and Theorem are stated for 2-layer Transformers only, the constructed solutions can be trivially extended multiple layers by e.g. letting the higher layers perform the identity function, or removing Assumption and allowing the model to flexibly use or ignore positional information. More precisely:
For Transformers with greater width, our Theorem applies directly, since the construction does not depend on the width.
For Transformers with greater depth, it suffices to show that additional layers can perform the utilize the residue link in the Transformer layer and choose
identity function. To this end, the value matrix to be zero and the FFN (with or without residue connection) to be identity. This
Whee d = 0, does not matter since there is unmatched open brackets.
26

---

construction is implicitly assuming LayerNorm will map zero vector to zero vector, which is true for the common PyTorch implementation and for our paper. Also, worth noting that this holds for both the architecture we considered in the paper and the standard GPT-2 architecture.
C.3 Proof of Corollary 1
Corollary 1. There exists 2-layer Transformer with uniform attention and no position embedding (but with causal mask and starting token 17] that generates the Dyck language of arbitrary length.
Proof. We will first construct uniform attention first layer that can generate the embedding in Equation (15). Suppose Z is the one-hot embeddings of a prefix p of length n, where each token of type for & [2k] is encoded as or and the starting token is encoded as O2k+1. Then it holds that
2h
Zo c. (c () (W (W
Σ 1=1
# #token of type in p}o, + 02++1-
(30)
an+1
Then we can choose W such that for x E 2
(W./ 2)1 Σ 221-1 T25
(W =12k+1,
(W x), =0, vi 2 3.
Hence it holds That
2) [w zo (o (2 (w(( 2)) 21 :,411
#ddeph of pnto1 + 02.
zo is then easy to check LN ([wx)) zo (c. (W 2) (w 2))
Z is uniquely
:,+++11 15 there exists a 2 2-layer
determined by the type and depth of pn without repetition. Then by Lemma
([w/²) Zo (C- (W (1) 2) (W 2)
ReLU MLP with width D2) that can map LN
Ze to the embedding in Equation
[5 It is then easy to that the condition in Theorem is
satisfied as wr(2) w = O. Hence the second layer can be constructed to let the Transformer to
output the correct next token probability.
C.4 Approximate Balance Condition For Finite Length Training Data
Theorem [ assumes the model reaches the optimal loss for Dyck prefixes any length. However, in practice, due to finite samples and various sources of randomness, training often does not end exactly at a population optima. this case, the condition in Theorem I not precisely met. However, for models that approximately meet those conditions, will prove that when the second-layer projection function g( is Lipschitz, a similar condition as in Equation 14 is still necessary.
We will show this by bounding the amount of deviations from the perfect balance. The idea is that for two long prefixes that differ in only the last open bracket, correct next token prediction requires the Transformer outputs on these prefixes to be sufficiently different, hence the part irrelevant the prediction (i.e. matched brackets) should not have a large contribution.
To formalize this intuition, let's define two quantities: Sa,d A. which measures the effect from one matching pair, and 2) Pa.j which measures the effect on the last position from all tokens in a prefix.
Here the starting token is necessary because otherwise, the Transformer with uniform attention will have the same outputs for pretix p and prefix 4 in which @ denotes concatenation, i.e. @ means the same string repeated twice.
27

---

Let be defined as in Equation 12 Sa,ara is defined as
Sd.d' a.j [0()] u(Taj.d: T2i,d'1)) u(T2j,d: F2i-1,d));
(31)
which measures how much a matching pair brackets (T24,d'-1 1,5-1,d') ) changes the input to the LayerNorm upon seeing the last token 7aj.d- Note that under the perfect balance condition, Sa,d" i.j (.(002)== 0.
The second quantity Pa., [B(2) is defined via intermediate quantity Q(2j, d, E): for any i e [k], [D) and length-(d 1) prefix i [2k] Q(i, (. t) is defined
Q d, t) == u(T2x,d-1, (s) +
Σ
u(T2i,d-1, at)
(32)
15d'<d
+ 1T
+ d2 Ri,d-1).
where is denotes the d' entry of f. Intuitively, Q(i, L) denotes the unnormalized second-layer attention output the last position, given the input sequence i 72
For results this subsection, suffices to consider prefixes consisting only of open brackets. Let t arg j (21-1)/E [[Q d, 2) and let t' denote the prefix that minimizes [|Q d, O)ll2 subject to the constraint that t' differs from at the last (i.e. (d - 1) position, i.e.
arg
min ( 4 tfa
d(2j,d,t))
Such choices of t, t' guarantees that the two prefixes differ the last open bracket and hence must have different next-word distributions. Finally, define
Pa.j0(0) = [ d, t')ll-
(33)
In the following theorem, Pa. will be used as reference to upper bound Sa.æ A. the model should not be sensitive to the insertion of matching pair of brackets.
[0(2),, meaning that
Theorem 3 (Approximate Balance). Consider 2-layer Transformer T (Equation 100 with minimal first layer (Assumption ! and a y-Lipschitzz g(2) for >> O, trained on sequences of length N with the mean squared loss (Equation (5))
Suppose the loss is approximately optimal, namely, the set of second-layer weights 0% satisfies L(T D...D.N) S gN-Ne, for any positive integer N >> 8D and sufficiently small >> O. Then, there exists constant C.,,,.D, such that v0 S d' S D, S d D,i,j E [k), holds that
S|S a. 1
Cr.DD N
P
(34)
states that when the loss L(0) is sufficiently small, Sa, . (0(2) must be small relative to Pa, Incquality 34 can be interpreted relaxation of Equation 14 which is
Intuitively, Theorem
equivalent Sa.a j.j 2)
0. The proof of Theorem shares similar intuition as Theorem and
is given in Appendix C.4.I
A direct corollary of Theorem additionally consider weight decay, in which case approximate balance condition still holds, as the regularization strength goes to
Corollary 3. Consider the setting where a Transformer with a fixed minimal first layer is trained to minimize Lx Lo(x)) + X 119112 which is the squared loss with X weight decay. Suppose (1)) 2-layer fully connected network and (2 of the Transformer is a 6-layer
of the Transformer fully connected network. Then, there exists constant C >> O, such that if a set of parameters 0x.N minimizes L then it holds v0 < d' < D,
D, j J. [k) that,
C N
VN, EAN, such that AX E AN]. S4. .. 10 <
Pa.10(2
X.NI-
We use @ i to denote the concatenation of two strings t, same as in Equation 15 denote the concatenation of two tokens Ti, 7j-
16
and use 7:7) to
28

---

C.4.1 Proof of Theorem 3
Proof. The key idea is similar the proof of necessity in Theorem [ That is, will construct two input sequences with different next-word distributions, and show that the approximate balance condition must hold that inserting (a bounded number of) pairs of matching brackets does not collapse the two predicted distributions given by the Transformer.
Constructing the input sequences.
l), and let denote the prefix that minimizes [|Q d, 8)ll2 Let arg men 1 [|Q(2j, subject to the constraint that must differ from in the last (i.e. (d - 1) position, i.e.
= arg
min PE[A]
d2).
The motivation for such choices of t, t' is that since they differ at least by the last position which an open bracket, they must lead to different next-word distributions. Note also that Pa.y [0(2) = [[Q(2j, I-)
With the above definition of t,, t', consider two valid Dyek prefixes pi and P2 with length no longer than N, defined as follows: for any d, d' E [D], [k), consider a common prefix
p 72--1 T2i 1T-1122--00 12... 12 2i.... 72j where Tı denotes token with type whose
d' open brackets
pairs
depth implicit from the context. Set Pr. P2 as
P1 = p t 12)-
P2 = p 1 + 125-
That is. P1, P2 differ in the last unmatched open bracket. In the following, we will show that the approximate balance condition must hold for the predictions on P1,P2 be sufficiently different.
Bounding the difference in Transformer outputs. For Transformer T with second layer parame- ters ((2) its outputs P1 P2 satisfy
IT 21 (p1) T00
(35)
llp
P2ll2 11710
P1 ||T (p22 P2lla
(36)
|PPI -p2ll 1
(1TTO
Pill 11 (p2) - -p2l1)
(37)
V2k
1
P2) (1) (since L(TTO D.M.D,n) S (N
(38)
V2k
-0(1),
(39)
where TV P2) denotes the TV distance in the next-word distributions from pl and p2, and o, (1) means the term will go to zero as goes to zero. The TV distance is lower bounded by the construction of Pl, P2. where differ at the last open bracket. The enror e upper bounded because of the assumption on ((2) i.e. L(T N D...D. & q -~>e with sufficiently small c.
Define by Ap the contribution of to the attention output (before LayerNorm) of the last position of P1,P2:
Ap
(u(T25,d-1, To,,""- +
( u(T25,d-1, (25-1,"")
1 S <d
N 2d' - -2d
(u(T2j.d11:72 + u(T2fdd1, T26-1d'41)
(40)
The attention outputs (before LayerNorm) of pı, P2, denoted by A(pi) and A(p2), satisfy that
P1A(pi) P (A, + d() P A(p2) P. P1 Q d,))).
(41)
29

---

Note that for any prefix p'.
TIoK 2 Kp') = =g -g. (PLA(P))) + e(T2(.)))
(42)
=g(²) (1 PLA(D') |PLA('')| + +e(Tear)))
(43)
where g(²) is Ly-piccchi, Hence the Lipschitz constant with respect to and we have
PLA((p) P_A(P2) || IP (PI)(1)) [PP14(P2)122
V2hr TV(p1, P2) - -1)
2
22 (1)
(44)
We show that Ap should not be too much larger in norm than Q(2j, Q(2j, t'). First, let's state a helper lemma about the contrapositive:
Lemma 1. For any O, there exists constant Re, such that for any a, b E IRd and any Rd such that ||lla 2 R. max ( [||l2, [bbll]] it holds that
rr
||b + rl12 11 Sc E.
b+r
a + rlla
Proof. Denote ro == (|all///|2..1 [b]]2]] Then R. : 4nu + suffices:
r + r+ b
1
1
10
||b||
|||||
|| + all2
||r + bll2
|r+ all
|| + b1l
||
all
||r +
bl
2ro
< |r||
+
|||||
||||| +
|||||
2ro
(1111
||r||
+ +1)
4ro
4ra
$
S
||ll| - rr
|r||| + ro
||||| ro
R.
Lemma
Saaimam@imlliii iimpies that if A, is too large, then the output on Pr. P2 (Equation 44
won't be sufficiently
different. Let Pa,, (0() be defined as in Equation (33) and let R. be the constant in Lemma need bound |P1Apl by
we
|P S Pall
(45)
As Equation 45 holds for p with any d, d', if one choose d' this shows
4R, Pa, a 10 lll2
[lu(Tgja-1, 12,,1 + 1,
72. 1.2 S
(46)
N
Further, it holds that for any 1 d' < 1
Σ
(u(Te),-1,,aa.0 + ul (2j,,l1, 126---1)))))))
1sd" <d
N
2d 2d
(u(Taj,d-1) T2.,d + u (
Σ
(u(T2jd-11 T2.," (7
Isd" +1
N 2d' - -2d 22
(u(Taj.d1, w (2- 2|2 < Pa (a.10 112
The triangle inequality then yields,
30

---

N -22 -2d -2d-2 -2
(u(r2j,d-1; + u( (2-1,,2))))
2
- (T( ((2)).d-111-- 72- S Pa.00
Because N 2 8D, we have that N-2d'
hence it holds that
2
(u(T2jd-11, 72,,0+111) + T2jj.d-11 1, 1,4
16R P Pa. 10 1112
- [u( 72i,d u 72j,d-1, 7 12-11
N
Combined with Equation (46). one can conclude that,
16DR, Sa. 3.j = [| -1) + u(T2j,d-1 Tei-1 18111-1111
P 10
1112.
(47)
N
The proof is then completed.
L
Proof of Corollary 3
This proof is in fact a direct combination of Theorems ] and 3 By Theorem T
we know there exists a weight ((2)* that can reach zero loss for arbitrarily length N. Then holds that ||0x,N ll2 I ||0(2)*|| (x.N minimizes the regularized loss. Noticing that bounded weight implies
bounded Lipschitzness of g! g(2), the rest follows as Theorem
C.5 Proof of Theorem
We now show the limitation of interpretability from single component, using argument by pruning from large random Transformers.
Theorem 2 (Indisiiguisshabiiiyy From Single Component). Consider any L-layer Transformer 'T (Equation (1O)) with embedding dimension m, attention dimension m. and projection function as 2-layer ReLU MLP with width w. For any E (0, 1) and N N+, consider AL-layer random Transformer Thanee with embedding dimension Margg = (m log Logg//// Lm/5)), attention dimension Marge,a = Om L log MamLL ), and projection function glarge as 4-layer ReLU MLP with width Wlarge Omax m, L Log wmL.N
Assume that [| < 1 for every weight matrix W in and suppose the weights are randomly
sampled as W.j (1,1,1) for every W E Thange Then, with probability 1 - over the randomness of Turree there exists nonstructural pruning (Definition 4 of Tuurge. denoted Trange which
approximates T with respect || 1| for any input X E R m satisfying X |X|1,22
Proof. We will first introduce some notation. For vector R" and y R will use Q y denote their concatenation. We will use 0" to denote the all-zero vector with dimension a. We will also assume without loss of generality that 2m. 20
We will use X to denote
0 (mmuagge maiiig--m''a X for X E Rm'x xN with m' S Maarge-
In the following, random network refers network whose weights have entries sampled from uniform distribution, i.e. Wij ~ U(-1,1) for every weight W in the random network.
We will first recall Lemma 2 from Pensia et al. (2020) which shows that a pruned 2-layer random network can approximate linear function.
Lemma 2 (Approximating linear function; Theorem of Pensia et al. 2020) restated). Let W E Im xm ||]| = (1). then for a E (ReLU, I}. where I represents the identity operator, for a random network g(x) (w with W2 E Ipmm xh, W, E Thhxm for hidden dimension
Here input and output dimension Tirge is actually Margg which larger m. additional dimensions are padded with zeroes. The norm constraint can be casily extended to an arbitrary constant. We can always pad dimensions if is too small.
31

---

h = (m logí vem' }}, with probability 1 - 8. there exists boolean masking matrices M1, M2. min such that for any R
1lM2 R W2 (( @ Wi)ae) W S Se||o]12,
where 3 denotes the Hadamard product.
We then derive two approximation results Lemmas and based on Lemma
Lemma 3. Under the setting of Theorem 2 with probability 1-26/3, 2. for any L E [L], 14--111 11. let
T be the 1-th layer Tf , there exists pruning of the (1' )-th and the (1')-th layer Tranze ;
named The -1) Thage such that when defined on domain |X 1.2 S 2T, X E BRMNN
1. - is independent of the last Marge
rows of the input.
2. The TTrrge)) (X) is an (10001:2)
AL-3
c-approximation ( with respect to 1, 2-norm.
Lemma Under the setting of Theorem 2 for any matrix W E 4mm44m [ S 1, with
probability - 8/4, for any [AL], there exists a pruning of the 1-th layer Targe named Targe" such that when defined on domain X E T
1. large is independent of the last marge 4m of the input.
2. a(x:) = norm.
-11)) large
X
is an C
4L
e-approximatton of g(X) WX with respect to 1, 2-
The proof of Lemmas
3 and is deferred to Appendix C.5.1 We can now prove the theorem.
We will first show with induction that if we 1) prune the (21 1)-th and 21-th layers of Tiagee to
approximate (1) for each [L]. and 2) prune the 2L to 4L-th layers Thrge to approximate
identity, then the pruned large transformer will be an e-approximation of T for any input 1 S 1.
We will perform induction on Let (1:1) define the composition of layer to I, i.c. (1:0 :- T o (1--1)
41--31 c. Suppose that T is an (1+ 1), since each attention output has bounded norm of and every weight matrix in projection function has spectral norm smaller than 1, hence the norm will at most increment (due to residual connection) after each layer. We have that
(1)) (X), and define 4 := (1000L>
E- E--aproximaation of (1:)), Note that [
T11-20)
(x)
|
S 41 < 4L.
Then according to Lemma 13 (1+ is (1 200 (CO -ipscchitz the of intermediate outputs (7(1211)
|
1.2 I 1}. We also have that (1:))()) is (1 2000. /CC/CC/---Lppphhic Now
1:m we can apply Lemma
to show that Thango
(1:2142)
can e'appprxximate (1:++1) with
C
1L-3
C
4L-3
d q1 2000 20012//C++++ (C)
(1 11+2002//77
110003
1
c
C
46-1-1
110072
C
The induction is then completed and we have the composition of Tirge for i [2L] approxxiisss the composition of T with E 1000
C 3L-3
c. We will then perform another induction showing
that the composition of Tri for E [2L e-- e---apprxximates T with 771 (100
C 3L-3-1
Suppose the statement holds for L > 1 > 0.
32

---

The induction step is similar, because we have T is (1 2002 /00L2/CC+ /C) Lipschitz, by Lemma it holds that the composition of Tage for E [2L I 1] approoximates with.
(1CC)
AL
è' C+L te
11000L2
(1 20002 + CLLLE
100002
C
3L-1-1
Sc
1000L2
c= c C1++1.
This concludes the induction and prove the first claim of the theorem. For the second claim, notice that through similar induction steps, we can prune arbitrary layer of Targe to approximate identity function and obtain the same approximation rate, this concludes the proof for the second claim. 0
C.5.1 Helper lemmas for Theorem
Error Analysis Our first lemma shows that the composition of e-approximation can approximate the composition of the original function.
Lemma Under the setting of Theorem 2 for any matrix W E R 4m ,|W S 1, with
probability 1 8/4, for any l' E [AL], there exists pruning of the 1-th layer Tiage named T such that when defined on domain X RR
1. Tiae is independent of the last Maarge 4m rows of the input.
2. a(x) = - X is norm.
C
e-approximation of g(X) W X with respect to 1, 2-
1000L
Proof. One can prune the value matrix layer I' to zero and the rest is direct consequence of 2emmas
Lemma 5. Given three metric spaces A, B, C equipped with same metric || I|- Suppose fi A f2 B C are ei, eg-approximations of 91, with respect to where 9ı is a Lipschitz function with constant a with respect to || and (I)] S Λ2σ, then it holds that, fi o f2 is an é' é-approximation of gi 92, with (A2 ( + E2) A112
Proof. For any Rdi holds that,
- (1))) S +|||=||
This then suggests that,
[[<({(())) (x()))))]
<1]f((f(())) - (oo 92(2 (x))
+ (x)]
-
<eallgn + (A2 +=)l
< (Ezλ) + + [x]|
Approximating ReLUMLI MLP We will first show an extension of Lemma illustrating that a pruned wide layer ReLU MLP approximate any 2-layer ReLU MLP.
R.4m parameterized by W1 2/2, for any 5,e E 1), consider random 4-layer win parameter- ReLU MLP f with input and output dimension 4m and width w' = O(w log( miu(e,8y) ized by Wiarge, with probability 1 1-6 over the randomness of weight of f. there exists a nonstructural pruning of f named f. such that f is an approxximttion of f with respect 2-norm.
Lemma 6. Consider any 2-layer ReLU MLP
4m
Rimxw W2 E Rwxim ||Wll [
33

---

Proof. Choose 6o = c/8. We only need to show there exists boolean matrices M1. M2, M3. M4. such that.
(M4 o a RoLU W Wa (eLLse) Wiarge,2 Viirse @ Warge, 12)))
W2ReLL (W)x) Se.
By Lemma a E 1mm
there exists boolean matrices M1 E R='x4m x4m and M2 R such that for any
My (low
Wi
+ W 2aage,
ReLU((M @ 1large,1)z)
0 -w ll2 S co||0|12.
M2
Hence we can choose M2
Ol w) xwx
and have fi(x) (MagWaaae2))LLL((((C
(R
Wx) cp-approximation of (z)
0"'-w
Again by Lemma there exists boolean matrices M2 E Rw'xe and M4 R4mxw", such that for any y R",
(M4 aaagge,4) ReLU (Mr, Ow x(wxx((w) O (w )) S collu/12
Hence we can choose M3 [Mg. Ow'x (ww" and have f2(x) = ReLU((M4 @ W Warge, (1) (eLU @ W())ge.))=)) is ao-approximation of g2(x)) W22.
is also easy to check 91 and Ø2 are both l-psshitct and 91 g0) By Lemma
we conclude
that f = fi O f2 is e'-approximation of = C J2. with = 4v 2Eo + e S 6.
This lemma then yields the following corollaries.
Corollary 1. Under the setting of Theorem 2 with probability 1 8/4, 4, for any E [4], [4L]. (1') there exists pruning of the projection function Blarge named Klarge such that
(1')
(1) giarge independent of the last Miarge
m dimension of the input.
(Co C m 1) is an 1000L2
gg) (z)
2. a(x) Slarge
(1')
C
E-approximation of g(x)
with
(mmargg
respect to 2-norm.
Proof. One can construct such pruning by pruning the last Maarge rows of the weight of the (t') last layer and the last Maarge m columns of the weight of the first layer of Blange to zero and then apply Lemma 6
Approximating Attention Patterns We will now show that the attention pattern can be approxi- mated by pruning random Transformer layers.
Lemma 7. For any 8, (0, 1). for any W E Th. Rmm xm where m' Om log( min((c,5))) suppose X pmxN then there exists nonstructural
[|]| S 1, for two random matrix W1, W2
pruning of W1, Wz. named W,, Wz. such that
| T W, - -
W 1o0 I <e||X|i,2
Here adopt [l] in vector sense, meaning the entry with largest absolute value.
Proof. Suppose without loss of generality, || S According Lemma 2 there exists nonstructural pruning W1, Wz, named Wt, W7, such that for any x E IR" ||x < 1,
|| T WAr Wxll2 s
34

---

This then suggests that,
IlyT W22 - W eellulla e.
This concludes the proof.
The next lemma shows how error propogates through the softmax operators.
Lemma 8. For any dimension d, suppose z, y E I2 satisfies || y11 S then it holds that,
exp(x:) 2i=1 1= exp(xii
exp(y:)
S Sex((2e)
1=1 exp(y:)
Proof. One can observe that,
exp(-e) exp(y) I (xp(e)
This then suggests,
exp(xi)
- exp(vi) - exp(2c)
exp(xt)
Σ i= exp(x:))
-= exp(y:)
Σ exp(x;s)
Hence,
exp(
exp(1i) exp(y))
S max(cxp(2c) - 1, exp(-2e) cxp(2c) -1
- exp(x:)
1=1
This concludes the proof.
Approximating Attention Module We will need the following lemma showing there exists pruning of the value matrix hare such that it has eigenvalues with magnitude (1).
Lemma 9. For a matrix W E mi Xmmarre,, with probability at least 1 - IOI there exists a pruning of W. named W', such that all the nonzero entries is contained in a x submatrix of W' that satisfies that (1) all its eigenvalues
6
within ( 1), (2) the index of row specifying the submatrix and the index of column specifying the submatrix are disjoint.
Proof. As Wlarge (m log( 8 )), hence can split Wi; [miarree /2], Miaggu /2 LeMtaagge into (m x (m blocks, each with width at least Oloog( (m)) 21 Within each block, with probability 1 10Lm
5
there exists at least one entry that has value at least 3. We can then choose d disjoint entries in W that are all at least 2. indexed with {(a;, b hie[a] where a; < aj and b; < by for < j. We can then prune all other entries to zero. Consider the submatrix defined by entries (a, b) for a E {a. Jim and b E Hem. Then, this submatrix will be diagonal and contains eigenvalues within (g. 1). Further {a, Jem and fbe must be disjoint because a, I [ 2 < 6, The proof is then completed.
We will also prove that LayerNorm with nonzero normalization constant is Lipschitz. P
Lemma 10. For LayerNorm function defined as LN(x) y,y Rm it holds that,
max P E R", for any
[N(x)) LN(W)
< 21 vlle/C.
Proof. We will proceed by case analysis:
1. If |1141,, PLulll < C, then LN(x) - LN(3)
||_
P < || yl12-
If 11 /Piylp C, then
PP
P vlla
P =lla PI
S 211x-10 -11x-yla vl-vl12-
P vila
210(-) hides absolute constants arising from the change of basis in the logarithm.
35

---

If || C and PLyllle C. then [N(2)) LN(3)
P x- P--Piill PLul2
|P |P zاl2
Piul2| & æ
yll2-
PIMl
The cases exhaust all possibilities, thus the proof is completed.
Finally, will need lemma showing how enror accumulates when consider both attention patterns and the value matrices.
Lemma 11. For any dimension and positive number N. for P.Q. E Iddd satisfying that || |1Q1|2 1, for any BAxN, if matrix A RNNN ,BE RAX satisfy that,
|| o(x T 1x)]1111111111111111111111 61.
| P 62
Vi, V [N]
Σ
A₁.* Ap,s 2 O.
JE[N]
Then holds that,
[BA - (xo Q2)1l12 & (eil| E2). [ILNc(B)) - LNc(Pro( Qx))lli.2 s 2(eil|PX|l1, (orool/))))ll
e2)/C.
Proof. For any E N, we will have
(BA).,+ - (Pzo (.x) 11
Σ
B, - (o(x (o(xTQx)) (PX) 1|
JE[N]
~| Σ Asa(PX):s - (o(x Qz)) 9. (PX):s
+ E
Aj. (PX B) ll2
JE[M]
jE(N]
S|| 1,2
Σ AAs (a(x (x))) is + +|PXX B||1,2
JE[M]
<||PX| 1.2||A al (=) PPX 1 12
The rest follows from Lemma 10
LayerNorm of larger dimension can be made to be functionally equivalent to a LayerNorm of smaller dimension. Precisely:
Lemma 12. Given any dimension d <, d', holds that for any TR.d
0 [
Pix [Nc(2)]
LNo(
Proof. The proof follows directly from definition.
We will now formally define attention module.
Definition 7 (Attention Module). We will define attention module al X Wv, WK. Wq)
a(X) = LNc (Wv (IXXXTIIWX))
Lemma 13. Attention module is lipschitz with respect to 1, 2-norr for bounded imput. Precisely, consider attention module (Definition DDefiition/pparrmmeterice parameteriied by ||y 11. [W l|2, [Wqll2 $ 1 with imput domain X |1,,2 I 4L, a(X) is 200L " with respect 1, 2.2-nom..
36

---

Proof. We have that
((X) INC (W W No
Choose to be sufficiently small constant, such that, exp (32L)) 11 64Le. Consider X and X satisfying that X X | and ||,1, 4L,
X
1.2 S 4L, will have
x I WoX (x) W (x)
-.)) (X.: x) W (X.,) ( [ W +X))+ x.)) W X.,)
<8LE + è 16Le.
By Lemma this implies,
| WX o((x) (W exp(322c) - 64Tc.
We also have
IWVv (x-x) 11,2 sc
|| 4L
Lemma 11
then implies that
|la(X) a(X)l11, 200T.
This then concludes the proof.
We can now prove that a large Transformer Layer and an attention module of the larger Transformer can be pruned approximate the attention module of a smaller Transformer Layer module.
Lemma 14. Under the setting of Theorem 2 with probability - 8/2, for any E [L], [4L 1],
let a be the attention module on the I-th layer of T, there exists a pruning the (I' 1)-th layer Targe named qil' -1) and the attention module l'-th layer o'args named ofurge such that when defined on domain [11,2 S 2L.
1. (1--1) is independent of the last Miarge m rows of the input. large
( (Ghagge
-Tulse""
([o
x ((meaare- -m) xN ())xx()))
1)) is an (100012)
4L-1
e-approximation of (x)
1:m
with respect to 1, 2-norm.
(1'--11) 1, 2-nor.
x ( m))xN 1)) 1am
4L e-approximation of X with respect to an 100014
4L and prune in the following order. It holds that Proof. We will use the shorthand co C for 1, exp(812e0) < 16.2eo-
We will prune W w-large.(')) according to Lemma and name the pruned matrix W-laries((") By Lemma 9 all the nonzero entries is contained in d x d submatrix of W that satisfies that all its eigenvalues are within (2, 1). We will assume WLOG the submatrix the one specified by row 1...d d and column 1..... 2d and name the submatrix as W.
2. We will then prune T (1'-1) according to Lemma 4 to output cp-approximation of X E B + large
X W-1p wi X
As W is defined as the submatrix pruned by w((++)) it holds that
0 (maggg
2m)xN
X
(1')
P D
W W-IPA X (Tiingge ml XN
37

---

3. Finally we will prune Wllarge(1')) Wlaage,(1") up to 6n error.
K
according to Lemma
approximate (W W
we can now calculate the approximation enror. For any X
E R
||11,2 S 2I, suppose
X
(x)) = W WV-IP_W Pl W X + 82
ml 2mm) x N
Then by our constrution, it holds that E (1,2), 1,211,22 S call X 111,22- We would then have
W Walarge.10 (1) (((()))(())))))))) (X) = Pi W: X + W (ylroo ( -m -
(1') d2
(48)
By our construction, it holds that ||W 82111,2 s 21102111.2 S 200l x 11 Further, by the construction of W w- (a))
(1)) it holds that, Q
|| ( W (ar (x0
(wlarion (1i
-W x + b1) (W x wi 60
(49)
As for any i,j E [N]
(W X +
X w(( (W x) W
T X
(W (1) x)) (w 01):0 +| (1 x):a/ // (1) 6))
2 (2e0 + + S X 12,200
combined with Equation 49
[1(we
W Whharge.(1) 7 (00 -
(w X) W x
S S |4
(50)
By Lemma 8 this implies
o (Wiriss. (T (
(ww x) 1(() x 11:1 I 4eo(1 +
122))
(51)
By Lemma
Equations and 51 imply,
W large, (1') T ( (( (X)o
W Iarress (1') (1 ((=)))x)) (w
(( (1
P1 W Xo (W K
x) X)TW() x 11 88o + 4|| (222 X S 80L
(fmiarge N
Now according to Lemmas
10 and 12 it holds that
(
1)
lafange 7((-11)
T
(x)11) S 160L"2o/C.
1:mm
This concludes the proof.
38

---

Approximating Transformer Layers We will finally show that two random Transformer layers can be pruned approximate given Transformer layer.
Lemma 3. Under the setting of Theorem 2
with probability 1 26. for any L E [L], E 1444-14, 11. let T be the I-th layer of there exists pruning of the ((' (1'-1) 1) and the (th)-th layer T TTorze
named large Taag such that when defined on domain [ 1,2 S 2I, X E BMXN
Ti" -
T is independent of the last margge m rows of the input.
2. large
large
(X) is an (1000L=)
41-3 c-approximation of T)) with respect to 1, 2-norm.
Proof. We will prune the (?' - 1)-th layer and the attention module of the 1'tth layer according
to Lemma to approximate a (1) and the projection function of the 1' layer according to Corollary
Notice that aa (X) + X
I ( + 1)|| X 1.2 and g(()) is lipsshiii, according to Lemma
1.2
1)) 1:m
Thu
3 T('--1) 1)
is an é' approoximation of (z), with
m)xN
2 C
C
4L
C
4L-2
C
8L-2
C
4L-3
é' s
1)
e
1000L2
1000
1000L2
1000L2
This concludes the proof.
C.6 Technical Lemmas
Lemma 15. Given any dimension d and number of samples n, for any size-n dataset {( y1) hee with a; E Rd and yı E R, there exists width-2n two-layer MLP J Rd IR with ReLU activation such that, f(x:)) y: for any E [n].
Proof. We will first choose direction Rd, ||w||2 1 and margin y 0 such that for any i + in [n). it holds that,
(w, x - az)) 2 2y.
We will assume WLOG wt x; is increasing in
Then we will construct an auxilliary series 2, for E [n] such that,
21 = -11/7
2, = 11/7 -
e m2.
Finally consider the following two-layer MLP with ReLU activation,
((x) Σ Z,ReLU ((w, x æ.) + +7) - z:ReLU ((w, x xz) 7),
will show that f f(x,) ys for any i [n]. Notice that
0,
ReRL (w,, - -x,) +7) ReRL ((w, x, - -x,) -))=
72s; = 1
22y2j, <
Thus holds,
a f(x,) Σ
2j ReLU ((w, x.)) + +7) 2, RRRLLU ((w, 2 - =x,) -7)
j=1
i-1
Σ
2yzj 724 V4.
==1
39

---

Lemma 16. Given any sets faitsem satisfying that E RR" and 24 F O. there exists a set of orthonormal vectors {uy)sE(n-2, of TR" such that (1) ug 1 = for any j E [n na-3 2| and (2) Ejeln-2 Uj Bu # for any E [m].
Proof. There exists a vector v E IR such that v' orthonormal basis {ug)je(n=2) of R the basis of the normal space of span(e, 1"). Then the lemma holds.
T xy * for any E [m]. We can then construct
IT
Lemma 17. Given any dimension n and constant M, there exists a 2-layer width-2 2n ReLU network f: R + R such that for any I E [0, MI", y E [n]. f(x @ y) Zy
Proof. The construction as followed, we will choose f as
[(x + 1) = Σ ReLU(x; + M(y 1))
Σ ReLU(x + M(y 1ou-i-11 M(y - 1).
Then as we have
M, is 1;
ReLU(x; + M(y 1))
Σ
ReLU(x; + M(y - -i- 1))
Iir i= y
0, i i2 4 1.
The proof is completed.
Lemma 18. Given any dimension n and constant M > 0, there exists a 2-layer width-2n ReLU network f IR" Vj & i, 2 = 0, it holds that f(z)= =
such that for any x R satisfying there exists i E [n], 24 > M and
Proof. The construction as followed, we will choose f as
m
f(x) Σ i (ReLU((x;) ReLU(x; M) M) /M.
The proof is completed.
Lemma Given any dimension n and natural numbers K, m, M. there exists K different 2-layer width-m ReLU networks Jk. R + R, then there exists 2-layer width-2 2 i ReLU network
k = fx(x)) when x E [0. M).
f: R + R, such that f(
Proof. Suppose that
m
fx(2) = Σ
ak ReLU + bu.e) + dy.
Then we can construct
s(
ax.s a ReLULLL + bu.i + M(y - k)) Re. + bu + M(y - k 1))
1
bk
Ck ReLU(y++ -1-k),
where Ck. satisfies
Vi, K.
(K +1 M
0K
The proof is then completed.
Lemma 20. Given any dimension and W R || la S 2, there exists 2-layer width-2n
ReLU network f R -+ IR such that for any E R", it holds that fxx Wx and both weight matrices parameterizing f has spectral norm less than 2/2.
40

---

Proof. The construction is straightforward, one can choose
f(x) [n, -nn] ReLU ([-Wa) ))
C.7 Discussion on Architecture Choices
The reader may notice that Equation (6 is not the same as the standard GPT architecture,
f((x: =
1 (IN
W Xo (c (W K x) (w x)) x))
(52)
We will shortly discuss the impact of considering Equation 52 here.
With similar arguments to Theorem 3 and the necessity part of Theorem one can prove that similar balance conditions should also hold for a transformer with layer specified by Equation (52) and minimal first layer that can nearly perfectly generate bounded Dyck languages.
However, the sufficiency part of Theorem I nno longer holds, when the balance condition holds, the + (W X) (W x)) will converge to zero when input length last column of the term W Xo (c (c+
converges to infinity. Hence, if not all e(Tr,a) where is closed bracket aligns with 1" then it is impossible for the model perfectly generate Dyck for arbitrary length. Although it remains possible to refine a sharper condition for standard GPT architecture to perfectly generate Dyck Language, we find considering Equation (6) more elegant in theory. We also verify with experiments that our architecture with standard training can learn bounded Dyck language to more than 97% accuracy. Also, the learned attention patterns are also similarly not interpretable standard architectures.
41

---

D Experiments
D.1 Training Details
we train 2-layer standard GPT on Dyck2,4 with sequence length no longer than 28, For (a), we train with hidden dimension and network width 200 and learning rate 3e-4. For (b), (c), (d), train with hidden dimension and FFN width 50 and learning rate 3e-3.
For Figure N
For Figure for (a), we train 1-layer transformer without residual link, FFN and the final LayerNorm before the linear head. The hidden dimensions and FFN widths are fixed as 500. For (a), we train the network with learning rate le-2 and for (b), (c), (d) we train the network with learning rate 3e-3.
D.2 Additional Results on Dyck Prefix
In the experiment presented in the main text, perform experiments complete Dyck sequences, which is a special case Dyck prefixes. this section, we present additional experiments on Dyck prefixes Dyck2, 2,1,88
Attention Patterns We first perform experiments on attention patterns. The qualitative results shown in Figures and 9 We can observe that the attention patterns are still diverse and do not commonly show stack-like patterns. We also calculate the attention variation and find that the attention variation is 0.34, based on 30 models with minimal first layer and different random seeds. In contrast, for models with a standard first layer and without position encodings, the attention variation is surprisingly high, reaching 14.51. The high value is caused by the large distance between attention patterns like Figure (c) and (d); that is, between patterns that attend more to the current positions, and patterns that attend more heavily the initial position. The difference is even increased when we consider longer sequence (Figure R). Similarly, the variation is also high for models with linear position embedding, reaching 11.92. This shows that the attention patterns still diverse and do not commonly show stack-like patterns.
(a) With Position Embedding
(b) With Position
(c) Without Position Embedding
(d) Without Position Embedding
Embedding
Figure 7: Second-layer attention patterns of two-layer Transformers on Dyck Prefix: Models for (b). are under the same setup but different random seeds; similarly for (d), All models reach 2 97% accuracy (defined in Section 4.1) In the heatmap, darker color indicates larger value. As we can observe, the attention patterns still show much variance.
Balanced Violations We also test the relationship with the balance violation with length general- ization Dyck prefixes, similar to Figure 3 We observe that although the negative correlation is not presented as the case of Dyck sequences, contrastive regularization still helps reduce the balance violation and significantly improve the length generalization performance. This shows that for Dyck prefixes, while the balance violation may not be predictive of the length generalization performance, it is still possible to reduce the balance violation and improve the length generalization performance. The results are shown Figure
Recall from Section 4.1 that the attention variation between two attention patterns At, As E NxN is
detined as Variation(AI, A2) || A2l
42

---

SIICO SIROOSI
STICO S(LLO)
(a) Position Embedding Run
(b) With Position
(c) Without Position
(d) Without Position Embedding Run 2
Embedding Run
Embedding Run
Figure 8: Second-layer attention patterns of two-layer Transformers on Longer Dyck Prefix: Models for (a),(b) are under the same setup but different random seeds. All models reach 2 97% accuracy (defined in Section 4.1). In the heatmap, darker color indicates larger value.
D.3 Extended Experiments
We include more experiments on the attention variation of different Dyck languages and architectures. The results summarized in Table
#types
Grammar depth m
#Layers
Layer
Layer
Layer
2
4
2
0.047 (0.06)
7.721 7.721 (0.908)
2
4
3
0.070
5.072(0.645)
24.063
2
8
0.087
(.583(0.961)
2
8
0.059
(.560
23.590
3
4
2
0.182 (0.044)
9.313(0.815)
3
4
3
0.225
8.426(0.877))
25.749
3
8
0.178(0.028)
(0000().884)
3
8
0.154(0.036)
6.280
25.451 (0.871)
Table 1: Extended attention variation. "Layer shows the mean (and standard deviation) of the attention variation on layer i, calculated on 40 sentences. The embedding width and FFN width are fixed as 50 in the experiments. We train using sentences from Dyck,, of length less than 28 and test the variation on 40 randomly sampled sentences with length 19 (the sampled sentence is fixed across different architectures). The random attention variation baseline here is 3.33. The numbers in this table are different from previous discussion, since the results here are from a slightly different architecture than the standard GPT-2 architecture: residue link is appended after the LayerNorm to match our theory better. The models are trained to convergence and have in-distribution accuracy higher than 97%.
Attention pattern visualization for three-layer experiments. The first-layer attention is close to uniform, while the ligher-layer attention shows no clear patterns.
(a) Embedding
15 run
(b) Embedding 15 run 2
(c) Embedding 17
(d) Embedding 16
Figure 9: Second-layer attention patterns of two-layer Transformers with a minimal first layer:
(a). (b) are based on embedding [5 with different random seeds. (c). (d) are based on embedding
17 a6] Different embedding functions lead diverse attention patterns, most of which are not
stack-like.
43

---

3.5
Contrastive
Balance Violation
3.0
Default Training
Figure 10: Relationship Between Balance Violation and Length Generalization. Ac- curacy from Transformers with minimal first layer with embedding 13] using both standard training and contrastive regularization (Equa- tion (18)). We again observe that contrastive regularization helps reduce the balance vio- lation and improve the length generalization performance.
2.0
1.5
1.0
0.5
0.800
0.825
0.850
0.875
0.900
0.925
0.950
059
Length Generalization Acc
(a) seed = 0
(b) seed =
(c) seed = 2
(d) seed =
Figure 11: Third-layer attention. The test sentence fixed and the attention patterns learned by different 3-layer models with the same architectures on the same dataset show large variation visually.
44


Reviews:
[{"review_id": "77mzxL3iO7", "reviewer": "Reviewer_QYzn", "summary": "Recently several efforts have been made to understand the exact mechanism that a trained Transformer uses to make its predictions. A number of those works rely on analysing the attention patterns or other components of Transformers. Broadly, this paper argues that in some cases it may not be possible to identify the mechanism used by Transformers by analysing individual components such as attention patterns. \n\nThey confine their analyses to Dyck languages with bounded depths -- which is the task of determining whether a sequence of brackets is well-balanced. For a two-layer Transformer which is expressive enough to recognize Dycks, they first show a condition for attention operation which is necessary and sufficient to construct a Transformer that can generate Dycks optimally (or almost optimally). The first layer in their construction is something called a minimal first layer which they define and then they show that if the attention in the second layer satisfies certain properties then one could construct the ReLU FFNs in such a way that the 2-layer Transformer can generate Dyck and obtain near-optimal mean squared error. The result essentially implies that there exists multiple Transformers with different attention patterns that can generate Dyck near-optimally including uniform attention and therefore attention patterns may not necessarily be informative of the mechanism used by the network.\n\nThey then show that Transformers with constant normed weight matrices can be approximated by pruning randomly initialized large Transformers (which have 4x layers and width). Lastly, they conduct experiments with Transformers trained on bounded Dyck languages. They compare the attention patterns of trained Transformers with different initializations and find that there is significant variance in the attention pattern on a string from the Dyck language.", "questions": "(Q1) MSE vs cross entropy: Is there any particular reason why the theoretical results are with mean-squared error and the experiments are with cross-entropy?\n(Q2) Dyck-1: Do the results hold for Dyck-1 as well? Previous works have shown how to interpret Transformers [1] and LSTMs [2] trained on Dyck-1. For languages like Dyck-1, a stack-like mechanism is not necessary and these works show that Transformers and LSTMs learn to do it with a counting mechanism. However, since bounded Dyck languages are regular, it is not necessary to emulate stack-like mechanism to recognize bounded Dycks as well. Maybe it could be useful to conduct experiments with Dyck-1 and see if the mechanism is robust. The task setup in [1][2] is different from the one considered in this paper. \n\n\n\n[1] On the Ability and Limitations of Transformers to Recognize Formal Languages.  \n[2] LSTM networks can perform dynamic counting.", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(S1) **Interesting theoretical results.** In my opinion both Theorem 2 and 3 are interesting to some degree. The fact that Transformers with various types of attention patterns and FFNs can solve the same problem in almost optimal manner is important to note while working on interpretability. \n\nDyck languages are also very important from a formal language theory perspective given the Chomsky–Schützenberger representation theorem -- which states that every context-free language can be represented by a regular and a Dyck language. It may be useful to readers to point this somewhere like the introduction.\n\n(S2) **Well-motivated problem.** Recently, mechanistic interpretability as well as experiments with Dyck languages have been the subject of various works, and these results could be useful to researchers working in the area. Although there have been several works in the past regarding the unreliability of attention for interpretability, the results in this paper provide more concrete evidence for a more well-defined task which could be useful. \n\n(S3) **Length generalization experiment.** I also found the experiments with more balanced attention in Section 4.2 somewhat interesting. Although it is for a specific case, it is interesting to see that insights from sections are directly applicable to improve the length-generalization performance.", "weaknesses": "(W1) **Implications of theoretical results.** An important thing to note is that the results prove the existence of Transformers with various attention patterns (and other components) that can solve the same task in a near-optimal way. It does not imply that Transformers with different initializations and hyperparameters can converge to each one of them uniformly at random (or a similar distribution). \n\nTo be clear, the authors make no such claims as well. The reason I think it is important to note is that similar evidence and arguments regarding generalization have been incorrect before. The fact that deep learning models have a large capacity (VC dimension, Rademacher complexity) which indicates that networks with various different parameterizations can fit the training set perfectly. This could be seen as an argument for the fact that it is not necessary for a network to converge to parameters that will generalize well. However, in practice when neural networks are initialized in a certain way and trained with GD, then they often converge to one that generalizes well and further work was needed to theoretically understand that. Similarly, I think it is important to keep in mind that even if Transformers can solve a task in many different ways, it is still possible that it is not the case when trained with gradient-based methods in practice. I think it could be useful to clearly explain this in the paper so that the reader does not infer incorrect conclusions.\n\n\n(W2) **Robustness of Experiments.** I do not think W1 is a major weakness or is needed to be immediately addressed, but because of the reasons mentioned in W1, I believe the empirical results are quite important. However, the experiments do not seem sound and rigorous enough to draw conclusions in a robust manner. For quantitative experiments in Section 4.1, is the average attention variation computed for just one input sequence \"[[[[]]]](((())))\" from Dyck-(2,4)? Let me know if I have interpreted it incorrectly. However, if it is the case, then it would be useful to conduct more extensive experiments indicating attention variation across multiple sampled inputs and for different Dyck languages such as Dyck-(2, 8), Dyck-(3, 24), etc. The number of random initializations (40) also seems quite small to me. It could be useful to see how the average attention variation is affected by the width and depth of the model. It should not be very computationally expensive to compute average attention variation across a large number of inputs (since it requires only inference) and the training time for these tasks should not be huge since it involves only synthetic data.\n\n\nI am happy to hear the author's response and change my score depending on that.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful comments and suggestions! We appreciate it that you consider our results as well motivated and theoretically interesting. Thank you also for the suggestion on Chomsky–Schützenberger representation theorem which will help better motivate the Dyck setting, and we will update the revised version accordingly.\n\n**(W1) The existence of multiple optima doesn’t mean SGD can find them.**\n\nThis is a great point and we completely agree with the reviewer on this. This is also one of the motivations of our work: despite the existence of the stack-like construction given by prior works, in practice it is not common for the model to converge to such a solution, as shown in Figure 1.\n\nOur results extend previous results by providing a much wider set of potential solutions, and we do not think it is probable that each solution would be uniformly likely to be found via standard optimization. As the reviewer pointed out, an interesting next step is to study how the “inductive bias” given by the synergy of the optimization algorithm and the architecture affects the solutions found, which we hope to explore in the future. By showing the existence of qualitatively very different minima, our result is a meaningful first step towards the future work of understanding which of these minima are more likely to be obtained through the training process.\n\nIn our paper, we also empirically verified that transformers trained using SGD/Adam do learn qualitatively different solutions. In particular, with common training setups or regularization approaches, there is no implicit bias towards learning the “more interpretable” attention patterns that prior works theoretically constructed. These observations support our overall claim.\n\nWe will update our camera-ready paper to clarify this point.\n\n\n\n**(W2) Robustness of the experiments**\n\nThanks for the excellent suggestions! We have conducted more experiments according to the reviewer’s advice. \nIn our current experiments, we perform experiments over bracket types $k$ in [2,3], grammar depth $m$ in [4,8], model layers in [2,3] and we calculate the attention variations on 40 random sampled sentences following the same distribution as training data (fixed set across the random seeds). We currently have $40$ random runs due to time constraint but we will add more runs in the future versions. For the detailed data, please see the appended pdf.\nThe takeaway from our result is that:\n- The choice of $k$ and $m$ in the regime of ablation study doesn’t have a huge impact of attention variation or the interpretability of attention patterns. We still observe vastly different attention patterns across runs with different seeds.\n- There exists a consistent trend that the attention variation will increase monotonously with layer. The attention patterns on first layer remain close to uniform for most runs while there could be vast differences between patterns on higher level of the models.\n\nWe are still running some experiments on models with different width and are happy to discuss the results after the experiments finished.\n\n**(Q1) MSE vs cross-entropy**\n\nThanks for the question. The theory actually doesn’t depend on the type of loss as the results characterize models at/near the minimum of the training loss. We will update our results in the following version to make this clear.\n\n**(Q2) Dyck-1**\n\nDyck-1 is an interesting setup that has been extensively discussed in prior works, though it is also an easy enough task, so that the next-word prediction task is solvable using only one layer of uniform attention (i.e. counting). This was pointed out in [1] as well. In contrast, our Theorems 1 and 2 are stated for second layer attention, and hence are not applicable to Dyck-1.\n\n[1] Satwik Bhattamishra, Kabir Ahuja, Navin Goyal. On the Ability and Limitations of Transformers to Recognize Formal Languages.\n"}, {"review_id": "oVlVpEmdgo", "reviewer": "Reviewer_46oE", "summary": "The authors discover interpretability conclusions based off attention weights can be unreliable with a case study on a Dyck language with a shallow transformer. Concretely, the authors show non-distinct attention patterns, even an uniform one can be theoretically learned to solve the Dyck language task which invalidates any interpretability conclusion based off solely on attention weights. The authors also try to prove this from formal theory as well as empirical results. Overall, the paper studies a timely topic and provides some insights, and has some open questions that may be addressed to make the paper more convincing.", "questions": "See my comments above.", "limitations": "See my comments above.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper overall is easy to follow.\n- The research topic about mechanistic interpretability based off attention weights seems like timely, and informs us about future works.\n- The formal proof on a shallow two-layer transformer with assumptions seems to valid the point that there are many attention patterns can be learned to solve the task, which makes the conclusions made based off a single set of attention weights less convincing.", "weaknesses": "-**Formal proof on a simple setup with assumption is good, but missing connections to larger transformer blocks**\n\nIt is great to have a starting point to start looking at the potential attention patterns can be learned to solve structural tasks like Dyck language with a lot of assumptions. But, it limits its connections to larger transformer blocks where there is no assumption about the first layer. After all, multiple stacked transformer blocks approximate high-degree of linearity than a single layer. Can also provide more explanations why their formal proof can be extended to larger transformer blocks?\n\n- **Different Attention Patterns Can Be Learned To Generate Dyck is not convincing enough**\n\nQualitatively to visualize attention patterns is fine as a start, but quantitatively only measuring attention weights difference among different initialization is bit lacking. It is well-known that, for structural generalization tests like this one, random seeds, learning rate and schedulers can large even affect model's factual behavior, let alone its hidden representations. The fact that attention weights are different is not surprising, and I feel like it is not enough to say different **effective pattern** can be learned to generate Dyck. For instance, if we can fix the attention weights to be uniform and enable gradients on other parameters, and show the model can still solve the task, it would be more convincing, correct me if i am wrong.\n\n- **Balanced attention increases generalizability is a weak evidence about the un-interpretability of attention weights?**\n\nIt is interesting to add regularizations to the attention weights can make the model generalizes better. But, by making the attention weights to distribute in a certain pattern can be viewed as a counter argument about the un-interpretability. Making them more balance is an interpretable mechanism to enforce; since it increases model performance, which means that interpretable attention distribution is somewhat better than randomly optimized ones. So, when performance is good, attention weights are better to be interpretable? I think some clarifications are needed here to connect to the main points of the paper.\n\n- **(Un)interpretability of Transformers is a very broad claim**\n\nI think this paper only studies the (Un)interpretability of Transformers' attention weights under a specific use case. So, it is may be better to position the paper to a narrower scope.\n \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the detailed reviews and the questions! We are glad that the reviewer appreciates the timeliness of the topic and our formal guarantees. Regarding the reviewer’s concerns, there seem to be some misunderstandings, which we would like to clarify below.\n\nTo avoid confusion in our responses, we’d like to first clarify the terms: we will use “(attention) weights” to refer to the model weights (i.e. parameters, such as $W_K$, $W_V$ matrices, or the MLP weights), and use “attention patterns” to refer to the intermediate output $\\sigma(XW_K W_Q^\\top X^\\top)$. Our results show that either attention patterns (Theorem 1,2) or weights (Theorem 3) are not reliable for interpretability.\n\n**(W1) Connection to larger Transformer blocks**\n\nRecall that we are trying to show that there exist more solutions than interpretable ones. Hence, the *simplicity of the model class is a feature and not a bug* (please also see [G1] of our global response): the set of solutions in more complex models (e.g. where the first layer is not necessarily minimal) is a superset of the set of solutions of the simpler models. In other words, we have shown that the solutions are not always interpretable even in a very restricted model class, and so they will not always be interpretable in a broader class. Also, our Theorem 3 shows that a small Transformer can be effectively simulated by simply pruning a large random initialized Transformer, which further strengthens our claims.\n\n**(W2) Effective patterns vs random variations**\n\nWe agree with the reviewer that there are inevitable variations introduced by hyperparameter choices and various sources of randomness, which do not necessarily correspond to different “effective patterns”. Nevertheless, as the reviewer pointed out, stack-like patterns and uniform patterns seem indeed sufficiently different. The reviewer suggested checking whether uniform patterns solve the task in practice, which is a great point and in fact *has been addressed in the paper*: it is currently stated as the last sentence of the first paragraph of “Sec 4.1 - Qualitative result”; will highlight this fact more in the camera-ready version. Please also see Appendix B.1 for additional discussions.\n\n**(W3) Does “improved balance improves length generalization” violate the uninterpretability premise?**\n\nThere seems to be a misunderstanding about the balance condition: the balance condition characterizes the optimal solutions (which exhibit perfect out-of-distribution generalization), and it doesn’t affect whether a solution is interpretable or not. For example, **both stack-like and uniform attention patterns satisfy the balance condition**, but the uniform attention is not interpretable. \n\n**(W4) (Un)interpretability of Transformers is a broad claim**\n\nWe agree with the reviewer that we should be cautious about the naming. In both the abstract and introduction, we have tried to be cautious about the types of interpretability methods our paper is tackling. Furthermore, we discuss in the related work section (Appendix A) that our results do not contradict all methods of mechanistic interpretability. We are happy to make concrete modifications that you think would improve the clarity of the scope of our paper. \n\nWe are happy to modify the title to hint at the types of methods we consider: for example, we would suggest “Myopic (Un)interpretability of Transformers: a case study with Dyck grammars”, to indicate the fact that we specifically focus on techniques based on inspecting individual components (either attention patterns or MLP blocks)."}, {"review_id": "fK9cO06oVm", "reviewer": "Reviewer_ksf8", "summary": "The paper studies the methods for interpretability of transformers that focus on individual parts of the model (instead of the entire network) using a synthetic setup of learning a Dyck language. Models that can solve this task need to satisfy the pumping lemma, and this is used to show that the attention pattern of a single layer can be nearly randomized without changing the network functionality. The consequential claim is that interpretability based on individual heads or weight matrices can be incorrect. ", "questions": "* The fact that we are considering bounded-depth Dyck language makes the classical results from formal automata theory not directly applicable - if I know the maximum depth of Dyck language, does the pumping lemma still apply? ", "limitations": "There are no concerns with respect to broader societal impacts.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+ Theoretical characterization shows a perfect balance condition on the attention pattern for 2-layer transformer corresponding to Dyck language. This condition admits non-stack-like attention pattern. \n\n+ As a consequence of lottery ticket hypothesis, it is shown that any transformer can be approximated. by a random larger transformer and thus, interpretability based on local components may not be reliable. ", "weaknesses": "* The paper appears to have a very narrow focus - examining the claim of stack-like patterns in the attention heads from Ebrahimi et al. Both stack-like and non-stack-like patterns can process Dyck languages. The presented analysis is not a \"proof\" or very convincing argument that the second is preferred by transformers. The presentation can be shifted to a critical examination rather than non-arguable claims. This is a minor presentation issue.\n\n* The title and initial discussion can emphasize the focus on bounded-depth Dyck language.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments and questions! We’d like to address the concerns below.\n\n**(W1) The results are not a “proof” that the non-stack-like patterns are preferred by Transformers.**\n\nWe’d like to clarify that “proving non-stack-like patterns are preferred” is not the goal of our paper. Instead, our results 1) formally prove that such non-interpretable solutions exist, and 2) empirically demonstrate that the non-interpretable solutions are not merely theoretical artifacts, but trained Transformers frequently converge to such solutions. The implication is that attention patterns alone are not reliable for interpretability. We are not sure if the reviewer had other concerns when referring to “non-arguable claims”; if yes, we’d appreciate it if the reviewer could clarify and we will be happy to discuss.\n\n**(W2) It should be emphasized that the setting is bounded-depth Dyck.**\n\nWe interpret this suggestion as emphasizing the “bounded depth” aspect since the title and abstract have both only stated Dyck. Though we do state the bounded depth assumption explicitly in Section 2, Problem Setup, we agree with the reviewer’s suggestion that it will be better to make it clear earlier in the paper—we will modify the abstract and introduction to reflect this suggestion. \n\n**(Q1) Question about the pumping lemma**\n\nBy the pumping lemma we are referring to the one for regular languages, which fits our setting since a bounded-depth Dyck language is a regular language (rather than a CFG). We will make this clearer in the future version, thank you for highlighting this!"}, {"review_id": "g9plIWT68P", "reviewer": "Reviewer_ZsLs", "summary": "This paper provides mathematical evidence that typical methods for interpreting the inner workings of transformers (looking at attention patterns, looking at feedforward weights) cannot be relied upon. The main argument of the paper is this: There is a task (specifically, language modeling of the bounded-depth Dyck-k language) such that it is possible for a two-layer transformer language model (assuming that it is trained on infinite data) to solve it perfectly using only uniform attention in the second layer (Corollary 1). The first layer can be one of multiple constructions proposed in prior work. Since uniform attention can hardly be considered \"interpretable,\" this shows that a transformer can solve a task perfectly without an interpretable attention pattern, so we cannot reliably draw conclusions from attention patterns alone. Theorem 2 removes the assumption that the model is trained on infinite data. Theorem 3 shows (I think) that for any sufficiently large transformer, it's likely that there is a fully-connected layer in one of the feedforward sublayers such that, if you prune weights in the whole transformer two different ways, resulting in two transformers that have different behavior, that layer can be pruned exactly the same way in both networks, implying that that layer can be interpreted ambiguously. So, we can't rely on analyzing feedforward layers in isolation for interpretability. The authors give some examples of attention patterns in transformers trained on this task that don't have clear interpretations and run experiments validating some aspects of their theory. They also propose a regularization term that helps the transformer generalize to out-of-distribution examples on the Dyck language.", "questions": "Most important questions:\n\n1. Eq 5: In this equation, layer norm comes before the residual connection. Isn't post-norm supposed to go after the residual? Is this a mistake?\n1. Eq 5: I think there's a mistake with how the causal mask is included -- it should be added to the softmax inputs, not multiplied, and the entries should have values of 0 or -inf, not 1 or 0.\n\nImportant questions:\n\n1. Eq 5: Will these results hold true if you use pre-norm instead of post-norm?\n1. 162: It might be quite difficult for a transformer to eliminate positional encodings, because of the residual connections. Would this interfere with your construction?\n1. Thm 3: Doesn't non-structural pruning have the ability to encode information in $T_{large}'$, merely with the pattern of which weights are pruned? Am I correct in understanding that the last part of Theorem 3 is meant to account for this? And that the significance of Theorem 3 is not that $T$ can approximate $T_{large}$, but that $T_{large}$ could be approximating one of multiple transformers $T_1$ and $T_2$, which have different behaviors? Won't $T_1$ and $T_2$ necessarily have similar behavior because they are similar to $T_{Large,1}$ and $T_{Large,2}$, and $T_{Large,1}$, and $T_{Large,2}$ are similar to $T_{Large}$? I think the answer is no because $T_{Large,1}$ and $T_{Large,2}$ are not necessarily similar to $T_{Large}$, but I wanted to clarify.\n1. Sec 3.2: I think this whole section would benefit from a more concise, intuitive description of the logical argument inside Theorem 3, and how it implies the statement made on 247. I'm still quite confused as to how this argument works. If $T_{Large,1}$ and $T_{Large,2}$ coincide on $W$ after pruning, how do you know that the weights pruned in $W$ do not account for the difference in behavior between them? Doesn't this argument only apply to pruned transformers then?\n1. 227: What is the main message of Corollary 2? Is it that Approximate Balance still holds true in the presence of l2 regularization, which is a common technique, but to a lesser degree for large $\\lambda$? Is there a large enough $\\lambda$ that it will fail to hold true?\n1. Do Theorems 1-2 work for transformers with more than 2 layers?\n1. 237: What is \"width\"?\n1. 279: As mentioned before, don't positional encodings complicate the construction, possibly explaining why there's a change?\n1. Fig 3: There are points that make it hard to believe there is a strong negative correlation. For example, some blue points have lower accuracy than orange points that have much higher balance violation. It seems like contrastive regularization helps, but likely in a way that isn't fully explained by balance violation.\n1. You showed that the transformer can solve Dyck without an interpretable attention pattern in the second layer. How do we know it doesn't have an interpretable pattern in the first layer? Do your experiments show that as well?\n\nOther questions:\n\n1. 120: Why is there a difference in loss function between the theory and experiments?\n1. Eq 5: What about dropout?\n1. 184: Which pumping lemma? For CFGs or DFAs? Can you elaborate on how the proof of Thm 1 resembles that of the pumping lemma?\n1. 208: Why can the loss not be optimal?\n1. 277: How many random restarts for these experiments did you run?\n1. Fig 1: How do you pick the models shown in this figure?\n1. 299: It doesn't seem that close to me.\n\nMinor questions and comments from reading:\n\n1. 27: Is it generating \"grammars\" or \"strings\"?\n1. 31: It's not like a stack, it is a stack. It can be recognized by a one-state real-time DPDA.\n1. Finite-precision transformers cannot recognize Dyck up to arbitrary depth.\n1. 35: works -> papers\n1. 37: I like the list of research questions.\n1. 51: Can you elaborate more on the significance of the non-stack-like attention patterns, and what non-stack-like attention is?\n1. 62: This finding is really interesting.\n1. 69: Interesting!\n1. 71: Works -> Work\n1. 88: works -> work\n1. 95: These brackets are balanced; the problem is that they aren't nested.\n1. Eq 1: This could probably be made a bit clearer.\n1. Eq 2: This is a bit hard to understand. Can you express it as an equivalent PCFG? The fact that all Dyck prefixes are included complicates this. Why is it important to include all prefixes?\n1. Eq 3: What is $e_{w_i}$?\n1. Eq 5: $g^{(l)}$ is a full feedforward sublayer, not just a feedforward network, right? The phrasing of this section makes it unclear.\n1. 135: What about positional encodings?\n1. 138: Is the whole LayerNorm operation set to the identity, or just some of its entries?\n1. 196: It would be helpful to point out why the proof of sufficiency is not necessary for the main argument of the paper.\n1. 200: Could you please include an intuitive proof sketch of Corollary 1 in the main text?\n1. 220: Can you elaborate on how this constraint can be satisfied?\n1. 238: With respect to what variables is O(1) constant? How is the l2 norm defined on a matrix?\n1. 241: What is the significance of using $1 - \\delta$ instead of $\\delta$?\n1. 242: Make it clearer that \\epsilon-approximate refers to the equation below.\n1. 243: It might be helpful to point out that this holds true when X is one-hot vectors.\n1. 280: Cool!\n1. 291: Quantitative is misspelled.\n1. 306: Can you include these results?\n1. 329: Ungrammatical sentence.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "This paper, in a mathematically rigorous way, answers a very important question: How much can we rely on naive ways of attempting to interpret the inner workings of transformers, i.e. looking at attention weights or feedforward weights? It turns out the answer is: not much. Although it might have been a bit obvious beforehand that looking at only one component of a transformer, and not the interplay between different parts of the network, is not necessarily reliable for interpretability, the authors prove this fact rigorously, which is an extremely valuable contribution. I think the bounded Dyck language was an excellent choice of case study: not so easy that the solution is trivial, but easy enough that the analysis is manageable. I think the overall logical argumentation of the paper is solid.\n\nA particularly cool result is that it's possible to train a transformer to solve the Dyck language while forcing the attention in the second layer to be uniform, which agrees with the theory. The experiments nicely back up the theoretical work.\n\nThe fact that Theorem 3 is a provable Lottery Ticket Hypothesis is also very interesting.\n\nOriginality: AFAIK this is an original and creative contribution.\n\nQuality: The methodology and mathematical rigor in this paper seem to be sound.\n\nClarity: Overall good, but I think this could be improved in places.\n\nSignificance: High. It has important implications for anyone working on interpretability and transformers.", "weaknesses": "**Edit:** I have read the rebuttal, and it addressed my biggest concerns.\n\nThe only reasons I have not immediately given this paper a higher score are that (1) I have some important questions in the Questions section I would like answered (2) I think the clarity of the paper could be improved.\n\nThe clarity issues have to do with the fact that the mathematical definitions and notation can get a bit overwhelming, and I would appreciate any attempt by the authors to simplify it and make it more readable.\n\nI think Section 3.2 requires a lot more clarification. I had a very difficult time understanding the logical argument, as there are several levels of nested quantifiers. I did not have time to check the proof in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their very detailed read and thoughtful comments!\n\n**M1 and l1 - LayerNorm: post or pre-norm**\n\nIn our theoretical setup, we have used a nonstandard order of layernorm and residual link. In real implementation, it is much more common to put LayerNorm after the residual addition, which happens after the output of attention modules is calculated (this is true in both post-norm and pre-norm).\n\nOur choice of architecture is to ameliorate the issue of over-smoothing of the softmax operation in the attention. Namely, it can be proven that if the residual is put before the softmax, there in fact **doesn’t exist any Transformer with a minimal first layer** that can reach zero loss on any length $N$. We will include the proof in the camera-ready version.\n\nIn the experiments, we try both our theoretical setups and standard GPT-2 setups and observe similar phenomena and accuracies. We choose to report the result with the standard GPT-2 setups and we will add a discussion on these architectural differences in the camera-ready version.\n\n**M2 - Typo in eq 5**\n\nThis is indeed a typo, thank you for spotting this! Please note that our conclusions and proofs are not affected by the typo.\n\n**I2 - Whether positional information can be eliminated completely**\n\nIt is not a problem even if the position information is present since later layers can always ignore it if necessary. More importantly, the definition of the minimal first layer is to present the smallest family of solutions, i.e. simplicity is a feature not a bug; please see [G1] in our global response for more discussions.\n\n**I3, I4: Clarification on Theorem 3**\n\nWe agree that pruning must encode information in the pruned Transformer and you are correct that the last part is accounting for this observation. You are also correct that the significance is that $T_{\\text{large}}$ can approximate two entirely different Transformers. It is also correct that $T_{\\text{large},i}$ won’t have similar behavior as the $T_{\\text{large}}$ the Transformer before pruning.\n\nWe are happy to add some remarks on the take-away message before the formal statement of Thm 3. What we are trying to argue is that if we investigate a single component like $W$ in T_{\\text{large},i}$, it is feasible that the same observation of $W$ may correspond to a completely different behavior of the Transformer as a whole. Hence, explaining the functionality of the transformer must take into account the interplay of multiple components. \n\n**I5: What’s the implication of Cor 2? Can lambda be arbitrarily large?**\nYour understanding is correct that Cor 2 means approximate balance still holds under regularization.\n\nLambda cannot be arbitrarily large: when regularization is added, there is a tradeoff between minimizing the Dyck language modeling loss and minimizing the regularizer. When lambda is too large, the focus is on the regularizer and hence the solution is no longer good for the Dyck language modeling task. For example, in the extreme of $\\lambda \\to \\infty$, all learned parameters converge to 0. \nIn contrast, our paper focuses on the more interesting setting of having a reasonably small L2 regularization constant (lambda), so that the original loss landscape is only slightly perturbed. When the original loss has multiple (approximate) optima, the regularizer serves as a tie-breaker by selecting the ones with a smaller norm.\n\n**I6: Can Theorem 1-2 be extended to beyond 2 layers?**\n\nYes, please refer to [G1] in our global response.\n\n**I7: line 237: Width refers to the MLP width.**\n\n**I8: line 279: Yes, this is the correct intuition.**\n\n**I9: contrastive loss doesn’t explain the full story**\n\nYes, we agree that the effectiveness of contrastive regularization is likely not fully explained by balance violation, and it is interesting future work to understand the training dynamics under various forms of regularization.\n\n**I10: How do we know the first layer doesn't have an interpretable pattern? What do the experiments show?**\nFirst, we’d like to clarify that our claim is not that “any component in Transformers is not interpretable,” but rather, “some component in Transformers may not be interpretable.” Hence our results do not imply non-interpretability of the first layer. As shown in the appended pdf in general response, the attention pattern of the first layer is close to uniform (loosely aligned with the intuition that the first layer performs counting) and is not very informative beyond this. \n\n**O1 - difference in loss function**\n\nPlease see [G3] in the global response.\n\n**O2 - Eq 5: What about dropout?**\n\nWe did not include dropout since it affects only the training dynamics, but not the loss optima. For example, it is common practice to disable dropout at inference time. \n\n**O3 - Is the pumping lemma for CFGs or DFAs? How does it relate to the proof of Thm 1?**\n\nOur proof idea is relevant to (but not a direct application of) the pumping lemma for regular languages (i.e. DFAs): although Dyck is context-free, bounded-depth Dyck is regular. The proof idea is to construct a family of prefixes p_m (m = 1,2,3,...), obtained by inserting m pairs of matching brackets to the original prefix p, which is similar to repeating the “middle component” in the pumping lemma.\n\n**O4 - Why can’t the loss be optimal?**\n\nWe were referring to the empirical limitation that training dynamics often do not exactly end at an optima in practice, due to finite samples and various sources of randomness. We will clarify this in our camera-ready paper. \n\n**O5 - How many random restarts for these experiments did you run?**\n\nWe have 40 runs per setup.\n\n**O6 - Fig 1: How do you pick the models shown in this figure?**\n\nIn each setting, we randomly selected models among those that reach at least 97% accuracy.\n\nThank you very much also for the other comments which will greatly improve the readability of our paper!\n"}]

Author rebuttal:
# Global response
We thank all reviewers for their time and effort in reviewing our paper, and for providing so many useful suggestions that will greatly improve the clarity and impact of our paper. Below we’d like to discuss some questions raised by multiple reviewers.

## [G1] Simplified assumptions: simplicity is a feature not a bug
Reviewer 46oE and ZsLs were curious about whether our conclusions or theorems can transfer to more complex Transformers. The answer is yes: the main conclusion of our paper is that interpretability based on a single Transformer component (e.g. an attention pattern or an MLP block) can be unreliable, since the set of optimal solutions can give rise to a large set of attention patterns and pruned MLP weights. When moving to more complex architectures, the set of solutions can only grow and complicate interpretability further, hence our main conclusion still stands. 
For example, even though Theorem 1 & 2 are stated for 2-layer Transformers only, the constructed solutions can be trivially extended to multiple layers by e.g. letting the higher layers perform the identity function. Note also that Theorem 3 is already stated for arbitrary number of layers and hence no generalization is needed.

## [G2] Scope of the paper
Reviewer 46oE and ksf8 suggested making the scope of the paper clearer by potentially modifying the title, abstract or the introduction, while agreeing that the setup has been clearly stated in later part of the paper (Section 2). In particular, it is suggested that we should highlight:
(Reviewer 46oE) the fact that we focus on interpretability methods based on individual components;
(Reviewer ksf8) the boundedness of the grammar depth.
We appreciate these suggestions, and propose to:
Update the title to be “Myopic (Un)Interpretability” and clarify in the abstract/introduction that our lower bounds do not apply to methods that study the model as whole, e.g. many mechanistic interpretability methods.
Update the abstract and introduction to clarify that we are working with Dyck languages with a bounded recursion depth.

## [G3] The choice of loss function
In our submitted version, we used different loss functions for theory (MSE) and in practice (cross entropy). As Reviewer QYzn and ZsLs correctly reminded, this discrepancy is in fact not necessary. We will update the camera-ready version to remove this difference.


## Additional experiments
we also provided additional empirical results per Reviewer ZsLs and QYzn’s suggestion. The figures and quantitative results are provided in the attached PDF and will be included in the appendix of the camera-ready version, and the details are deferred to the responses to individual reviewers.




Meta-review: This submission is a case study aiming to illustrate challenges in recent approaches to studying the interpretability of transformers. More precisely, it both theoretically and empirically illustrates that generalizing solutions to the problem of generating bounded-depth Dyck languages can have unintuitive structure. For example, a generalizing solution can employ a uniform attention mask (rather than one that reflects the matching of opening/closing brackets), showcasing that interpretability approaches focused on studying attention patterns in isolation are insufficient.

The reviewers agree that this is a timely paper that can and should influence future research on interpretability of Transformers. The mix of theoretical grounding combined with practical experiments was received positively, indicating that the paper could have robust impact.

Concerns were raised about the experiments (QYzn, 46oE), which the authors addressed in their rebuttal by providing additional data. Finally, reviewers raised a number of issues around the presentation of the results: smaller issues around clarity of the core paper, and a larger issue about the framing of the contribution. The authors have agreed to shift the framing slightly, and were receptive to feedback and clarification questions, so that I expect a future version of the paper to be substantially more polished.

Overall, I believe that this is an interesting paper that deserves presentation and discussion at NeurIPS.
Decision: Accept (poster)