Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammars

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.

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. A 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. The fact that Theorem 3 is a provable Lottery Ticket Hypothesis is also very interesting. Originality: AFAIK this is an original and creative contribution. Quality: The methodology and mathematical rigor in this paper seem to be sound. Clarity: Overall good, but I think this could be improved in places. Significance: 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. The 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. The 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. I 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.

Questions

Most important questions: 1. 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? 1. 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. Important questions: 1. Eq 5: Will these results hold true if you use pre-norm instead of post-norm? 1. 162: It might be quite difficult for a transformer to eliminate positional encodings, because of the residual connections. Would this interfere with your construction? 1. 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. 1. 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? 1. 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? 1. Do Theorems 1-2 work for transformers with more than 2 layers? 1. 237: What is "width"? 1. 279: As mentioned before, don't positional encodings complicate the construction, possibly explaining why there's a change? 1. 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. 1. 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? Other questions: 1. 120: Why is there a difference in loss function between the theory and experiments? 1. Eq 5: What about dropout? 1. 184: Which pumping lemma? For CFGs or DFAs? Can you elaborate on how the proof of Thm 1 resembles that of the pumping lemma? 1. 208: Why can the loss not be optimal? 1. 277: How many random restarts for these experiments did you run? 1. Fig 1: How do you pick the models shown in this figure? 1. 299: It doesn't seem that close to me. Minor questions and comments from reading: 1. 27: Is it generating "grammars" or "strings"? 1. 31: It's not like a stack, it is a stack. It can be recognized by a one-state real-time DPDA. 1. Finite-precision transformers cannot recognize Dyck up to arbitrary depth. 1. 35: works -> papers 1. 37: I like the list of research questions. 1. 51: Can you elaborate more on the significance of the non-stack-like attention patterns, and what non-stack-like attention is? 1. 62: This finding is really interesting. 1. 69: Interesting! 1. 71: Works -> Work 1. 88: works -> work 1. 95: These brackets are balanced; the problem is that they aren't nested. 1. Eq 1: This could probably be made a bit clearer. 1. 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? 1. Eq 3: What is $e_{w_i}$? 1. Eq 5: $g^{(l)}$ is a full feedforward sublayer, not just a feedforward network, right? The phrasing of this section makes it unclear. 1. 135: What about positional encodings? 1. 138: Is the whole LayerNorm operation set to the identity, or just some of its entries? 1. 196: It would be helpful to point out why the proof of sufficiency is not necessary for the main argument of the paper. 1. 200: Could you please include an intuitive proof sketch of Corollary 1 in the main text? 1. 220: Can you elaborate on how this constraint can be satisfied? 1. 238: With respect to what variables is O(1) constant? How is the l2 norm defined on a matrix? 1. 241: What is the significance of using $1 - \delta$ instead of $\delta$? 1. 242: Make it clearer that \epsilon-approximate refers to the equation below. 1. 243: It might be helpful to point out that this holds true when X is one-hot vectors. 1. 280: Cool! 1. 291: Quantitative is misspelled. 1. 306: Can you include these results? 1. 329: Ungrammatical sentence.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

4 excellent

Limitations

Yes.

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.

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. + 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. * The title and initial discussion can emphasize the focus on bounded-depth Dyck language.

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?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

There are no concerns with respect to broader societal impacts.

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.

Strengths

- The paper overall is easy to follow. - The research topic about mechanistic interpretability based off attention weights seems like timely, and informs us about future works. - 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** It 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? - **Different Attention Patterns Can Be Learned To Generate Dyck is not convincing enough** Qualitatively 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. - **Balanced attention increases generalizability is a weak evidence about the un-interpretability of attention weights?** It 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. - **(Un)interpretability of Transformers is a very broad claim** I 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.

Questions

See my comments above.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

See my comments above.

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. They 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. They 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.

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. Dyck 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. (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. (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). To 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. (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. I am happy to hear the author's response and change my score depending on that.

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? (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. [1] On the Ability and Limitations of Transformers to Recognize Formal Languages. [2] LSTM networks can perform dynamic counting.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

NA

Response

Thank you very much for your response. G1, I2, I6, I8, O2: Can you include a more detailed discussion of this point in the paper? The two specific examples you listed in G1 make sense, but the general claim "When moving to more complex architectures, the set of solutions can only grow and complicate interpretability further" is a very strong one, and it requires careful justification. I would recommend inserting a section that clearly lists all of the simplifying assumptions you make about the transformer architecture (e.g. number of layers, details about positional encodings), and explain how the results under these assumptions can still apply to unsimplified, general-case transformers. M1, I1: Thank you for the explanation, and for agreeing to discuss this more in the final version. Doesn't this architectural change significantly limit the applicability of the theory to real transformers? If it's not architecturally possible to construct a minimal layer, don't the main results of Theorems 1 and 2 fall apart? I3, I4: Thanks. I would appreciate it if you rewrote or added to this section in a way that preempts these questions. I5: I see. I was wondering if this Corollary gives us a finite $\lambda$ that breaks this condition, but I think it's weaker than that, because it tells us what happens as it goes to 0 in the limit, right? I10: Got it, makes sense. O1: Great! O3: Thanks. If you have space, could you include this clarification in the paper? O4: Great, thanks. O5: I missed this later in the paper. Thanks! O6: Thanks, this detail is worth mentioning. Typo in Fig 3: leas -> leads

Thanks for your response and I have raised my score.

Thanks for the response. It answers some of concerns. I raised my rating slightly. For the future versions, I would like to see more tasks such as parity. I think it will greatly strengthen the claim with other tasks, especially on those fixed attention weights settings.