Emergent Stack Representations in Modeling Counter Languages Using Transformers Utkarsh Tiwari, Aviral Gupta, Michael Hahn Abstract Transformer architectures are the backbone of most modern language models, but understanding the inner workings of these models still largely remains an open problem. One way that research in the past has tackled this problem is by isolating the learning capabilities of these architectures by training them over well-understood classes of formal languages. We extend this literature by analyzing models trained over counter languages, which can be modeled using counter variables. We train transformer models on 4 counter languages, and equivalently formulate these languages using stacks, whose depths can be understood as the counter values. We then probe their internal representations for stack depths at each input token to show that these models when trained as next token predictors learn stack-like representations. This brings us closer to understanding the algorithmic details of how transformers learn languages and helps in circuit discovery. 1 Introduction * * footnotetext: Equal contribution † † footnotetext: Senior author Modern day language models (LMs) are increasingly capable of capturing complex sequential and linguistic patterns, achieving strong performance across diverse natural language as well as synthetic tasks. Despite their impressive capabilities and substantial amounts of effort and progress, the inner workings of these models still remains opaque and un-interpretable to a substantial extent. For instance, we know that transformer models of sufficient complexity can learn, for example, to perform modular arithmetic, but recovering the exact algorithm used by these models to perform this task remains a challenge ( Nanda et al., ) . Building on this line of inquiry, our research focuses on formal languages, specifically examining models trained on counter languages—a class of languages formally modeled using stack memory. We demonstrate that these models develop internal representations that effectively mimic stack structures, providing insights into how they process and generate such languages. 1 1 1 Importantly, we do not make any claims about the causality of these stacks. This is further discussed in the Section 5. Interpreting, understanding and reasoning about the algorithms and circuits within language models (LMs) remains a largely open problem, with use cases in AI safety, alignment, and performance. Figure 1: High probing accuracy for the counter values at each token on a model trained to recognize counter languages as a next token predictor shows that the models learn a stack-like structures in their internal representation which is helpful in reasoning about and interpreting the learned algorithm to achieve this task. Formal Languages: Formal languages provide a useful testbed to isolate and investigate the learning properties of transformers and their failure cases, since these languages have precise mathematical properties that the model can be tested on ( Ackerman and Cybenko, 2020 ) . This literature contains both empirical results ( Strobl et al., 2024a ; Bhattamishra et al., 2020 ) as well as theoretical analysis of cognitive biases and learning bounds over these formal tasks ( Hahn and Rofin, 2024 ; Pérez et al., 2019 ; Zhou et al., 2023 ; Hahn, 2020 ) . This line of inquiry is particularly significant because all algorithmic tasks can be reduced to a language within a specific class of formal languages. For instance, arithmetic in Polish notation can be modeled as a single-counter, non-regular context-free language, solvable with a stack memory but not without it. Thus, robust theoretical and empirical insights into formal languages contribute to advancing the capabilities of language models ( Zhang et al., 2024 ) . Furthermore, natural languages exhibit features that can be approximately mapped to certain classes of formal languages, often displaying recursive structures akin to those found in formal systems ( Kornai, 1985 ; Jäger and Rogers, 2012 ) . Mechanistic Interpretability and Probing Classifiers: The field of Mechanistic Interpretability (MI) aims to extract the reasoning and interpretable structures present inside these models. Among other things, MI deals with identifying features inside language models ( Rai et al., 2024 ) . A feature is a human-interpretable property of the model’s activations on specific inputs. This leads to an understanding of features as meaningful vectors in the activation space of a model. A widely used approach to understanding model structures through the aforementioned features involves probing these models by linking internal representations or activations with external properties of the inputs. This is done by training a classifier on these representations to predict specific properties. Known as probing classifiers ( Belinkov, 2022 ) , this framework has become a key analysis tool in numerous studies of NLP models and the methodology that we use to understand the internal structure of the trained models on these formal languages. This direction is also motivated by other works which have had success in retrieving coherent internal structures like world models in natural language ( Li et al., 2021 ; Abdou et al., 2021 ) and toy/synthetic setups ( Elhage et al., 2022 ; Li et al., 2024 ; Vafa et al., 2024 ) . To our knowledge, this work is the first to leverage probing classifiers to analyze models trained on formal languages. To more formally define the training objective of the probes, let f:x\mapsto\hat{y} denote a language model, trained on a formal language, with performance measured by the language modeling task of auto-regressive next-token prediction. The model f generates intermediate representations f_{l}(x) at layer l , called embeddings. A probing classifier g:f_{l}(x)\mapsto\hat{z} maps these embeddings to a property z (e.g., stack depth, part-of-speech), trained and evaluated on dataset D_{P}=\{(f_{l}(x),z^{(i)})\} , which is formed by pairing each token’s embedding with its property in that sequence. The performance of the probing classifier depends on two key factors: the probe’s ability to map embeddings to the target property and the original model f ’s ability to generate information-rich embeddings by effectively learning the next-token prediction task. If the classifier achieves high performance, it indicates that the model has learned information relevant to the property being probed. This setup serves as a proxy for examining the internal structure of the transformer, by probing for implicit properties of the dataset it was trained on. However, the choice of property must be carefully considered to ensure meaningful and interpretable results. In our case, we adopt a more formal and structured approach by leveraging counter languages, which provide a well-defined and rigorous framework for probing. Formal languages offer a clear and systematic property to probe, grounded in their precise modeling and theoretical foundations. 2 Related Work Transformers and Formal Language Learnability: Transformers dominate sequence modeling tasks, but their ability to model FL requiring structured memory, like counters or stacks, is only incompletely understood. While theoretically Turing-complete ( Pérez et al., 2019 ) and universal approximators of sequence functions ( Yun et al., 2020 ) , practical learnability of FL is less understood. For example, Hahn (2020) showed Transformers struggle with Parity and Dyck-2 in the asymptotics of unbounded sequence length. Empirical studies, such as Bhattamishra et al. (2020) and Strobl et al. (2024b) , demonstrate Transformers can learn Dyck-1 and Shuffle-Dyck, suggesting they can simulate counter-like behavior. These findings highlight the need for further investigation into Transformers’ ability to model FL. Probing Internal Representations: Probing classifiers have become a key tool for understanding neural model representations. By training simple classifiers on intermediate activations, researchers infer whether specific properties are encoded. For example, Voita et al. (2019) studied attention heads, while Rogers et al. (2020) and Coenen et al. (2019) explored intermediate layer information. In FL, probing has been used to analyze models trained on tasks like arithmetic and syntactic parsing ( Li et al., 2021 ; Abdou et al., 2021 ) . Notably, Elhage et al. (2022) and Li et al. (2024) showed probing can reveal emergent structures in synthetic setups. Our work extends this by probing models trained on counter languages, providing insights into stack-like representations learned by Transformers. Enforcing Stack Structures in Transformers: Several works have explored explicitly incorporating stack-like structures into neural models to handle hierarchical patterns. For example, Joulin and Mikolov (2015) proposed a neural stack for RNNs, enabling pushdown automata simulation. Similarly, Suzgun et al. (2019) introduced a differentiable stack for learning Dyck languages. In Transformers, papers like Fernandez Astudillo et al. (2020) and DuSell and Chiang (2024) explored external memory modules to enhance long-range dependency modeling. While promising, these approaches require significant architectural changes. Our work focuses on whether Transformers can implicitly learn stack-like representations without explicit constraints, offering a more interpretable approach to modeling FL. In summary, our work builds on these foundations by analyzing Transformers’ ability to model counter languages and probing their internal representations for stack-like structures. By bridging FL theory and mechanistic interpretability, we aim to advance understanding of how Transformers learn and generalize algorithmic patterns. 3 Problem Setup And Architecture 3.1 Counter Language Modeling Counter Languages are languages modeled using counter machines, which are DFAs with counter variables which can be incremented, decremented, and set to 0. We focus our work on the Dyck language, which is a well studied class of counter languages, and the k -Shuffles of Dyck- 1 . Dyck-1 is the set of well-formed parenthesis strings, is a context-free language which requires 1 counter to model it. Over the alphabet \Sigma=\{(,)\} the production rules are: S\to\begin{cases}\epsilon\\ (S)\\ SS\end{cases} Shuffle is the binary operation || on two strings which interleaves the two string in all possible ways. Inductively: • u\odot\epsilon=\epsilon\odot u=\{u\} • \alpha u\odot\beta v=\alpha(u\odot\beta v)\cup\beta(\alpha u\odot v) for any \alpha,\beta\in\Sigma and u,v\in\Sigma^{*} 2 2 2 The * is the Kleene Star operation . For example, the shuffle of ab,cd = { abcd,acbd,acdb,cabd,cadb,cdab }. The Shuffle operation can be extended to apply over languages \mathcal{L}_{1} and \mathcal{L}_{2} as: \mathcal{L}_{1}\odot\mathcal{L}_{2}=\bigcup_{\begin{subarray}{c}u\in\mathcal{L}_{1},\\ v\in\mathcal{L}_{2}\end{subarray}}u\odot v We use Shuffle- k to denote the Shuffle of k Dyck-1 languages, each with vocabulary \Sigma_{i} such that \bigcap_{i\in[1,k]}\Sigma_{i}=\emptyset , i.e. disjoint vocabularies 3 3 3 Hence, Shuffle- 1 is the same as Dyck- 1 . Similar to Bhattamishra et al. (2020) Shuffle-2 is the shuffle of Dyck-1 over alphabet \Sigma = {(, )} and another Dyck-1 over the alphabet \Sigma = {[, ]}. Hence the resulting Shuffle-2 language is defined over alphabet \Sigma = {[, ], (, )} and contains words such as ([)] and [((])) but not ])[(. In our experiment setup we consider 4 counter languages: Dyck-1, and Shuffle-2, Shuffle-4, and Shuffle-6. For all these languages we follow the training details from Bhattamishra et al. (2020) 3.2 Language Modeling Architecture and Training Setup Model Architecture. We employ an encoder-only transformer model with a linear decoder layer (language-modeling head) for sequence processing tasks, following the setup from Bhattamishra et al. (2020) . Let \mathcal{V} denote the alphabet of the language, where each symbol v\in\mathcal{V} is treated as a unique token. Tokenization is a mapping \tau:\mathcal{V}\to\mathbb{Z} , assigning each token to a unique integer ID. The encoder maps input tokens x=(x_{1},\dots,x_{T}) to dense embeddings E=(e_{1},\dots,e_{T}) , where e_{i}\in\mathbb{R}^{d_{\text{model}}} , augmented with positional encodings P=(p_{1},\dots,p_{T}) to encode sequence order. The combined embeddings X=E+P are processed by a stack of n_{\text{layers}} transformer encoder layers. Each layer consists of: 1. A multi-head self-attention mechanism with a causal mask M , ensuring \text{Attention}(Q,K,V)=\text{softmax}\left(\frac{QK^{T}}{\sqrt{d_{k}}}+M\right)V where M_{ij}=-\infty if i