REVIEW 5 major objections 5 minor 1 cited by
Emergent Stack Representations in Modeling Counter Languages Using Transformers
T0 review · 5 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read This paper shows that small transformers trained only to predict the next token over counter languages encode stack-depth information in their hidden states, decodable by probes with high accuracy on task labels and near-chance accuracy…
desk verdict Modest probing study with a plausible but insecure stack-representation claim; needs held-out tests and a sharper interpretation before I'd trust it. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing equivalence is that a $k$-counter machine's counter values are exactly the depths of $k$ stacks: pushing an opening bracket increments its counter, popping a closing bracket decrements it, and a string is accepted exactly when no counter goes negative and all end at zero. The paper exploits this by training one probe per stack to predict the current depth from the transformer's final encoder-layer embedding at each token. A control task randomizes the depth labels for the same inputs, and the gap between task accuracy and control accuracy—selectivity—is the paper's evidence that the probe is reading a real feature.
What would settle it
A probe trained on stack depths up to $d$ should generalize to unseen larger depths if the hidden state literally tracks a counter; a model that only stores empty/nonempty status or relies on positional cues would fail there. Running that extrapolation test on the same checkpoints would settle whether the decodable quantity is the exact depth or a cheaper proxy.
Extended reading notes
Core claim
The paper's central claim is that a transformer trained solely to predict the set of valid next tokens on a counter language learns internal representations from which the exact depth of each counter stack can be decoded at every token. For Dyck-1 this is a single stack depth; for Shuffle-$k$ it is $k$ separate depths, one per stack. The probes—from linear classifiers to six-layer networks—achieve high validation accuracy on the real depth labels but near-random accuracy on a randomized control, so the paper argues the depth signal is genuinely present rather than an artifact of probe memorization. The paper is explicit that this establishes representational presence, not causality: the discovered depth code may or may not be the mechanism driving the model's predictions.
Load-bearing premise
The paper assumes that high probe accuracy for exact stack depth demonstrates a stack-like representation, even though the training objective only requires knowing whether each counter is empty or nonempty.
Editorial extensions
If this is right
- For the four languages studied, the final hidden state of the model contains decodable stack-depth information at every token, even with linear probes.
- Because control-task accuracy is near chance, the depth signal is not an artifact of the probe memorizing the training set.
- The pattern across languages—higher probe accuracy when stacks update less often—implies that representational prominence of a counter depends on how frequently the task forces it to change.
- The paper's own stated next step is to determine whether these decodable stacks are causally involved in generating predictions, since probing alone cannot show that.
Reading between the lines
- The exact-depth decodability is stronger than the training task requires: a closing bracket is legal exactly when its counter is nonempty, so the model could get by with a binary empty/nonempty state; the paper does not yet explain why exact depth appears.
- A natural extension would be to search for a single activation direction whose projection grows linearly with stack depth; such a direction would make the counter variable explicit and help locate the push/pop circuits.
- If the depth code is later shown to drive predictions, the same probe setup could map where in the layers counters are updated, connecting representational findings to circuit discovery; the paper leaves that causal step open.
- The same method could be applied to natural-language hierarchical structure, probing for embedding depth or agreement distance rather than bracket depth.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper trains small encoder-only transformers on four counter languages (Dyck-1 and the shuffle of k Dyck-1 languages for k=2,4,6) as next-token predictors, and then trains feed-forward probing classifiers on the last-layer token embeddings to predict the exact depth of each counter/stack at each token. High probe accuracy relative to a randomized-label control, together with a positive control on a Tracr-compiled transformer that explicitly computes the Dyck-1 balance, is interpreted as evidence that the models learn stack-like/counter representations. The authors explicitly disclaim any causal reading of these stacks and position the work as a representational, not mechanistic, result.
Significance. If established, the representational claim would be a useful contribution to the interpretability of transformers on formal languages, connecting probing methodology to a well-defined class of tasks with known stack semantics. The paper has several strengths: it uses formal languages whose stack/counter semantics are exact, it includes a randomized-label control following Hewitt and Liang, it reports a Tracr-based positive control that verifies the probe can detect depth when a model provably computes it, and it evaluates both linear and multi-layer probes. The main weakness is that the central inference from probe accuracy to 'stack-like representation' is not yet airtight, because the training objective does not require exact counter values and the evaluation is conducted in-distribution with no held-out generalization or error bars.
major comments (5)
- [Sections 3.3 and 4] The inference from high probe accuracy for exact stack depth to the presence of counter variables is not fully supported. The next-token prediction target for these languages is a k-hot vector in which a closing symbol is legal exactly when its counter is nonzero; exact depth is not required by the loss. The randomized-label control rules out memorization of the probe training set, but it does not rule out the probe exploiting a lawful correlation between depth and input-side statistics (e.g., token counts, position, or recent close durations) available in the hidden state without the model maintaining an exact counter. To make the central claim load-bearing, the authors should include a control that removes this confound, such as evaluating probes on held-out sequence lengths beyond the training range, comparing against a baseline model that provably tracks only zero/nonzero status, or using a causal intervention that ablates the hypothesized counter information.
- [Section 3.3 and Figure 3] The probing dataset is sampled from the training corpus with sequence lengths between 2 and 50, so the probe is evaluated only in-distribution. No held-out generalization to longer sequences or to sequences with a different depth/position distribution is reported. Because depth is correlated with sequence position and with counts of open and close tokens within this range, the reported accuracies could reflect length-specific shortcuts. The paper should report probe accuracy on held-out lengths (e.g., 51-100) and, where possible, on sequences whose depth distribution is decorrelated from position.
- [Section 4 and Figure 3] No error bars or multiple-seed results are reported for the probing experiments, so it is unclear whether the differences between Dyck-1 and Shuffle-k or between probe architectures are reliable. The central conclusion rests on a single evaluation run; at least five seeds with mean and standard deviation (or a significance test) should be reported.
- [Section 4] The explanation that higher Shuffle-k accuracy arises because each stack's depth changes less frequently is not tested. A probe operating on per-token hidden states could achieve high accuracy by predicting a token's depth from the depth at the previous token when hidden states are temporally smooth. The authors should report accuracy conditioned on whether the probed stack was updated at the current token, and on the size of the update, to rule out this trivial explanation.
- [Appendix B] The Tracr positive control demonstrates that the probing setup can detect depth in a model that explicitly computes the balance, but it does not address the converse failure mode: whether the probe would also detect depth in a model that only tracks zero/nonzero status. A negative control, such as a model trained on a regular-language approximation of Dyck-1 with similar token statistics, would substantially strengthen the claim that high accuracy is specific to models that represent exact counters.
minor comments (5)
- [Section 3.1] The displayed condition 'T i∈[1,k] Σi = ∅' appears to intend the intersection of the alphabets; please use the proper intersection notation and clarify the sentence.
- [Section 3.3] The phrase 'Keeping in the with the best practices' contains a word-order error; it should read 'in line with the best practices.'
- [Section 4 / Figure 3] The caption for Figure 3 says 'across model architectures for different stack depths' but the x-axis appears to show probe architecture or stack depth; please clarify the axes and the meaning of the blue and red lines.
- [References] Strobl et al. 2024a and 2024b appear to be the same paper (the survey of transformers and formal languages); please merge or distinguish the entries.
- [Appendix B] The appendix does not state explicitly how the probing target (stack depth) is derived from the Tracr-compiled model's activations; please specify the exact feature that is probed (e.g., the balance value in the RASP program).
Circularity Check
No significant circularity: probe targets are externally defined from the language and input, the Tracr control is independent, and the paper's self-citations are not load-bearing.
full rationale
The paper's probe target, stack depth (equivalently counter value), is defined directly from the language and the input string, not from the fitted parameters of the transformer, and the probes are evaluated on held-out validation samples from the same corpus while the model itself is trained only on next-token prediction. The Tracr/RASP compiled model is an external positive control from Lindner et al. and Weiss et al., not authored by the present authors, and it is used only to validate the probing methodology rather than to support the main claim about trained models. The randomized-label control follows Hewitt and Liang. The only author-overlap citations (Hahn 2020; Hahn and Rofin 2024) appear in the Related Work section on theoretical limitations of transformers and are not load-bearing for the probing result. The paper explicitly disclaims causal claims in Section 5, and while the inference from high probe accuracy to a 'stack-like representation' involves interpretive assumptions and potential confounds such as depth correlating with positional statistics, that is a validity concern rather than circularity: no equation in the paper reduces the conclusion to the probe setup or to the training objective by construction. The derivation chain is therefore self-contained with respect to the empirical claim, and no specific circular step can be exhibited.
Assumptions & free parameters
free parameters (3)
- Probing dataset sequence length range =
2 to 50 tokens
- Language model hyperparameters =
d_model=64, d_embedding=32, 1 layer, 4 heads, lr=5e-3, 25 epochs, batch 32
- Probe architecture and training hyperparameters =
linear to 6-layer MLP, hidden 128, dropout 0.2, lr=0.001, 10 epochs, batch 32
assumptions (4)
- standard math Dyck-1 and Shuffle-k are correctly characterized by k-counter machines, and counter values equal stack depths.
- domain assumption A probing classifier's high accuracy on in-distribution validation indicates the model's activations encode the probed property.
- domain assumption The next-token prediction task can be solved by tracking stack depths using counter-machine semantics.
- ad hoc to paper The Tracr-compiled RASP model correctly implements Dyck-1 recognition and serves as a valid positive control for the probing setup.
Cite this review
Pith. "Pith review of Emergent Stack Representations in Modeling Counter Languages Using Transformers." pith.science (2026). https://pith.science/paper/TEXFGBHD
@misc{pith2026250201432,
author = {Pith},
title = {Pith review of: Emergent Stack Representations in Modeling Counter Languages Using Transformers},
year = {2026},
howpublished = {\url{https://pith.science/paper/TEXFGBHD}},
note = {Machine review of arXiv:2502.01432}
}
read the original 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.
Figures
Figures from the paper (3 more)
Forward citations
Cited by 1 Pith paper
-
Unraveling Syntax: Language Modeling and the Substructure of Grammars
Language-modeling loss decomposes linearly over the sub-grammars of a probabilistic context-free grammar, and models learn these sub-grammars in parallel rather than in stages.
Reference graph
Works this paper leans on
-
[1]
Mostafa Abdou, Artur Kulmizev, Daniel Hershcovich, Stella Frank, Ellie Pavlick, and Anders S gaard. 2021. https://doi.org/10.18653/v1/2021.conll-1.9 Can language models encode perceptual structure without grounding? a case study in color . In Proceedings of the 25th Conference on Computational Natural Language Learning, pages 109--132, Online. Association...
-
[2]
Joshua Ackerman and George Cybenko. 2020. https://arxiv.org/abs/2006.01338 A survey of neural networks and formal languages . Preprint, arXiv:2006.01338
work page Pith review arXiv 2020
-
[3]
Yonatan Belinkov. 2022. https://doi.org/10.1162/coli_a_00422 Probing classifiers: Promises, shortcomings, and advances . Computational Linguistics, 48(1):207--219
-
[4]
Bhattamishra, Kabir Ahuja, and Navin Goyal
S. Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020. https://api.semanticscholar.org/CorpusID:222225236 On the ability and limitations of transformers to recognize formal languages . In Conference on Empirical Methods in Natural Language Processing
work page 2020
-
[5]
Andy Coenen, Emily Reif, Ann Yuan, Been Kim, Adam Pearce, Fernanda Viégas, and Martin Wattenberg. 2019. https://arxiv.org/abs/1906.02715 Visualizing and measuring the geometry of bert . Preprint, arXiv:1906.02715
arXiv 2019
-
[6]
Brian DuSell and David Chiang. 2024. https://arxiv.org/abs/2310.01749 Stack attention: Improving the ability of transformers to model hierarchical patterns . Preprint, arXiv:2310.01749
arXiv 2024
-
[7]
Nelson Elhage, Tristan Hume, Catherine Olsson, Nicholas Schiefer, Tom Henighan, Shauna Kravec, Zac Hatfield-Dodds, Robert Lasenby, Dawn Drain, Carol Chen, Roger Grosse, Sam McCandlish, Jared Kaplan, Dario Amodei, Martin Wattenberg, and Christopher Olah. 2022. https://arxiv.org/abs/2209.10652 Toy models of superposition . Preprint, arXiv:2209.10652
arXiv 2022
-
[8]
Ram \'o n Fernandez Astudillo, Miguel Ballesteros, Tahira Naseem, Austin Blodgett, and Radu Florian. 2020. https://doi.org/10.18653/v1/2020.findings-emnlp.89 Transition-based parsing with stack-transformers . In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 1001--1007, Online. Association for Computational Linguistics
Show all 31 references
-
[9]
Michael Hahn. 2020. https://doi.org/10.1162/tacl_a_00306 Theoretical limitations of self-attention in neural sequence models . Transactions of the Association for Computational Linguistics, 8:156--171
2020 doi
-
[10]
Michael Hahn and Mark Rofin. 2024. https://doi.org/10.18653/v1/2024.acl-long.800 Why are sensitive functions hard for transformers? In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 14973--15008, Bangkok, ...
2024 doi
-
[11]
John Hewitt and Percy Liang. 2019. https://arxiv.org/abs/1909.03368 Designing and interpreting probes with control tasks . Preprint, arXiv:1909.03368
2019 arXiv
-
[12]
Gerhard J \"a ger and James Rogers. 2012. https://api.semanticscholar.org/CorpusID:8765815 Formal language theory: refining the chomsky hierarchy . Philosophical Transactions of the Royal Society B: Biological Sciences, 367:1956 -- 1970
2012
-
[13]
Armand Joulin and Tomas Mikolov. 2015. https://arxiv.org/abs/1503.01007 Inferring algorithmic patterns with stack-augmented recurrent nets . Preprint, arXiv:1503.01007
2015 arXiv
-
[14]
Andr \'a s Kornai. 1985. https://aclanthology.org/E85-1001/ Natural languages and the C homsky hierarchy . In Second Conference of the E uropean Chapter of the Association for Computational Linguistics , Geneva, Switzerland. Association for Computational Linguistics
1985
-
[15]
Li, Maxwell Nye, and Jacob Andreas
Belinda Z. Li, Maxwell Nye, and Jacob Andreas. 2021. https://doi.org/10.18653/v1/2021.acl-long.143 Implicit representations of meaning in neural language models . In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th Internatio...
2021 doi
-
[16]
Hopkins, David Bau, Fernanda Viégas, Hanspeter Pfister, and Martin Wattenberg
Kenneth Li, Aspen K. Hopkins, David Bau, Fernanda Viégas, Hanspeter Pfister, and Martin Wattenberg. 2024. https://arxiv.org/abs/2210.13382 Emergent world representations: Exploring a sequence model trained on a synthetic task . Preprint, arXiv:2210.13382
2024 arXiv
-
[17]
David Lindner, Janos Kramar, Sebastian Farquhar, Matthew Rahtz, Tom McGrath, and Vladimir Mikulik. 2023. https://proceedings.neurips.cc/paper_files/paper/2023/file/771155abaae744e08576f1f3b4b7ac0d-Paper-Conference.pdf Tracr: Compiled transformers as a laboratory for interpreta...
2023
-
[18]
Progress measures for grokking via mechanistic interpretability
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
-
[19]
Jorge Pérez, Javier Marinković, and Pablo Barceló. 2019. https://arxiv.org/abs/1901.03429 On the turing completeness of modern neural network architectures . Preprint, arXiv:1901.03429
2019 arXiv
-
[20]
Daking Rai, Yilun Zhou, Shi Feng, Abulhair Saparov, and Ziyu Yao. 2024. https://arxiv.org/abs/2407.02646 A practical review of mechanistic interpretability for transformer-based language models . Preprint, arXiv:2407.02646
2024
-
[21]
Anna Rogers, Olga Kovaleva, and Anna Rumshisky. 2020. https://doi.org/10.1162/tacl_a_00349 A primer in BERT ology: What we know about how BERT works . Transactions of the Association for Computational Linguistics, 8:842--866
2020 doi
-
[23]
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. 2024 b . https://doi.org/10.1162/tacl_a_00663 What formal languages can transformers express? a survey . Transactions of the Association for Computational Linguistics, 12:543–561
2024 doi
-
[24]
Mirac Suzgun, Sebastian Gehrmann, Yonatan Belinkov, and Stuart M. Shieber. 2019. https://arxiv.org/abs/1911.03329 Memory-augmented recurrent neural networks can learn generalized dyck languages . Preprint, arXiv:1911.03329
2019 arXiv
-
[25]
Chen, Ashesh Rambachan, Jon Kleinberg, and Sendhil Mullainathan
Keyon Vafa, Justin Y. Chen, Ashesh Rambachan, Jon Kleinberg, and Sendhil Mullainathan. 2024. https://arxiv.org/abs/2406.03689 Evaluating the world model implicit in a generative model . Preprint, arXiv:2406.03689
2024 arXiv
-
[26]
Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. 2019. https://doi.org/10.18653/v1/P19-1580 Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned . In Proceedings of the 57th Annual Meeting of the Associatio...
2019 doi
-
[27]
Gail Weiss, Yoav Goldberg, and Eran Yahav. 2021. Thinking like transformers. In International Conference on Machine Learning, pages 11080--11090. PMLR
2021
-
[28]
Reddi, and Sanjiv Kumar
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. 2020. https://arxiv.org/abs/1912.10077 Are transformers universal approximators of sequence-to-sequence functions? Preprint, arXiv:1912.10077
2020 arXiv
-
[29]
Dylan Zhang, Curt Tigges, Zory Zhang, Stella Biderman, Maxim Raginsky, and Talia Ringer. 2024. https://arxiv.org/abs/2401.12947 Transformer-based models are not yet perfect at learning to emulate structural recursion . Preprint, arXiv:2401.12947
2024 arXiv
-
[30]
Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Josh Susskind, Samy Bengio, and Preetum Nakkiran. 2023. https://arxiv.org/abs/2310.16028 What algorithms can transformers learn? a study in length generalization . Preprint, arXiv:2310.16028
2023 arXiv
-
[31]
online" 'onlinestring :=
ENTRY address archivePrefix author booktitle chapter edition editor eid eprint eprinttype howpublished institution journal key month note number organization pages publisher school series title type volume year doi pubmed url lastchecked label extra.label sort.label short.list...
-
[32]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.