Pith. sign in

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 →

arxiv 2502.01432 v1 pith:TEXFGBHD submitted 2025-02-03 cs.CL cs.LG

classification cs.CLcs.LG
keywords transformerinterpretabilityprobingclassifierscounterlanguagesDyckshufflestackrepresentationsnext-tokenpredictionformallanguagelearning
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether transformer language models trained on formal counter languages build internal representations that track the languages' stack memory. The authors train small encoder-only transformers as next-token predictors on four counter languages—Dyck-1 and the shuffle of two, four, and six Dyck-1 languages—and then train probing classifiers to read the depth of each stack at every input token from the final hidden layer. The probes succeed with high accuracy, while randomized control tasks stay near chance, which the authors read as evidence that counter variables are present in the internal representations. The result matters because it suggests that next-token prediction, without any architectural stack or training signal for depth, can produce stack-like structure that circuit discovery could exploit.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 5 minor

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)
  1. [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.
  2. [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.
  3. [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.
  4. [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.
  5. [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)
  1. [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.
  2. [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.'
  3. [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.
  4. [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.
  5. [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

0 steps flagged · score 0.0 of 10

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 3 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the equation of counter values with stack depths and on the probing methodology. The only quantities chosen by hand are model and probe hyperparameters and the probing sequence length range. No new entities are postulated; the paper uses standard stacks and counters. The main conceptual load is the assumption that probe decodability of exact depth implies a stack-like representation, even though the task's input-output mapping only requires tracking zero or nonzero status.

free parameters (3)
  • Probing dataset sequence length range = 2 to 50 tokens
    The probe is evaluated only on short in-distribution sequences from the training corpus; the generality of the stack-representation claim is not tested at longer lengths.
  • Language model hyperparameters = d_model=64, d_embedding=32, 1 layer, 4 heads, lr=5e-3, 25 epochs, batch 32
    These hand-chosen settings produce the specific models probed; the conclusion that transformers learn stack-like representations could differ with scale, depth, or training budget.
  • Probe architecture and training hyperparameters = linear to 6-layer MLP, hidden 128, dropout 0.2, lr=0.001, 10 epochs, batch 32
    Probe capacity is selected by hand; accuracy may depend on probe size, and the paper does not report a capacity sweep or variance across seeds.
assumptions (4)
  • standard math Dyck-1 and Shuffle-k are correctly characterized by k-counter machines, and counter values equal stack depths.
    Used in Section 3.1 and Appendix A to define the languages and the probed targets; this is mathematically standard and not contested.
  • domain assumption A probing classifier's high accuracy on in-distribution validation indicates the model's activations encode the probed property.
    Section 3.3 adopts the standard probing assumption, mitigated by a randomized control task; it remains an assumption about representation, not causation.
  • domain assumption The next-token prediction task can be solved by tracking stack depths using counter-machine semantics.
    The paper assumes the counter or stack formulation is the natural algorithmic description, although the output only depends on zero or nonzero status of each counter, not exact depth.
  • 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.
    Appendix B uses a hand-written RASP program to build a positive control; this assumes the compiled model and program faithfully represent the algorithm and that success there transfers to trained models.

how reviews work

0 comments
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 reproduced from arXiv: 2502.01432 by the authors.

Figure 1
Figure 1. High probing accuracy for the counter values [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. The model is trained to predict the set of all [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Probing accuracy across model architectures [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: A graphical representation of a 1-counter [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: Behavior of the counter machine in 4 on (()) (top) and (()( (bottom) B Tracr Model Results As mentioned in 3.3 we compile a model using Tracr from the following RASP program for Dyck￾1 5 : def num_prevs ( bools ) { prevs = select ( indices , indices , <=) ; return ( in…
Figure 6
Figure 6. Figure 6: Probing results on the Tracr compiled model. [PITH_FULL_IMAGE:figures/full_fig_p009_6.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Unraveling Syntax: Language Modeling and the Substructure of Grammars

    cs.CL 2025-10 conditional novelty 6.0 of 10

    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

31 extracted references · 9 canonical work pages · cited by 1 Pith paper

  1. [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. [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

  3. [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. [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

  5. [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

  6. [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

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

  8. [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
  1. [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

  2. [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, ...

  3. [11]

    John Hewitt and Percy Liang. 2019. https://arxiv.org/abs/1909.03368 Designing and interpreting probes with control tasks . Preprint, arXiv:1909.03368

  4. [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

  5. [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

  6. [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

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

  8. [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

  9. [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...

  10. [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

  11. [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

  12. [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

  13. [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

  14. [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

  15. [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

  16. [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

  17. [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...

  18. [27]

    Gail Weiss, Yoav Goldberg, and Eran Yahav. 2021. Thinking like transformers. In International Conference on Machine Learning, pages 11080--11090. PMLR

  19. [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

  20. [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

  21. [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

  22. [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...

  23. [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...

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.