  Interpretability methods aim to understand the algorithm implemented by a
trained model (e.g., a Transofmer) 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 after severely
constraining 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.
