Elamur Research⌕
☰
home / papers / 2026 / Do Transformers Grok Succinct Algorithms? Mechanistic Evidence for Counting Circuits

Do Transformers Grok Succinct Algorithms? Mechanistic Evidence for Counting Circuits

Paper · 2026 · Yizheng Zhao

Summary

Theory predicts that fixed-precision Transformers can encode binary counting over exponentially many states with a compact, polynomial-size circuit, while recurrent models need exponentially many states. This paper asks whether gradient training actually finds such compact circuits or settles on shortcuts. The author uses LARGE COUNTER, a synthetic task in which a model autoregressively generates successive n-bit binary integers separated by delimiters. Small Transformers are compared against large LSTM, GRU, Mamba and Mamba-2 models, and the trained networks are then reverse-engineered with activation patching, attention analysis and causal abstraction, using Boolean RASP (B-RASP) as the reference construction.

Shallow Transformers reach perfect generalization, while the recurrent and state-space baselines largely fail. The working solution appears abruptly through grokking, at the same moment as a sharp drop in weight norm. Inside the model, attention heads retrieve the corresponding bit of the previous number, and MLPs compute the carry logic.

The work connects formal succinctness results with what trained models actually learn. It also provides a controlled reference circuit against which arithmetic mechanisms in large LLMs can be compared.

Key points

  • Architecture gap: A 2-layer Transformer (d=64) generalizes perfectly. LSTM/GRU models stay below 6% accuracy even at d=2048, and Mamba/Mamba-2 stay below 1.1%. This is consistent with the hierarchy Transformer ≫ LSTM > SSM.
  • Encoding control: Switching to little-endian encoding roughly triples RNN accuracy. The gap to the Transformer still exceeds 84 percentage points, so the bottleneck is architectural rather than a format artifact.
  • Learned circuit: RoPE-based "Same-Bit Lookup" heads attend a fixed n+1 tokens back to fetch the matching bit. MLPs behave like XOR/AND gates for carry propagation, matching the B-RASP construction.
  • Pythia probe: In Pythia-160M on 5-shot addition, "Arithmetic Heads" such as Layer 8, Head 5 attend to aligned operand digits. This only works with space-delimited prompts, because standard BPE tokenization breaks the fixed digit positions. The author treats this evidence as exploratory.
  • Main limitation: Success depends on stratified sampling that balances training data across carry-chain lengths. On naturally skewed data, models may remain stuck on heuristics.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Nanjing UniversityNanjing · China99 works · 8,510 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

🧭 Topics 1Research subjects and languages the work is about.Interpretability · 149 works

Cite

Cite as Yizheng Zhao. 2026. Do Transformers Grok Succinct Algorithms? Mechanistic Evidence for Counting Circuits. Findings of the Association for Computational Linguistics: ACL 2026.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.findings-acl.1301

@inproceedings{zhao2026do,
  title = {{Do Transformers Grok Succinct Algorithms? Mechanistic Evidence for Counting Circuits}},
  author = {Yizheng Zhao},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.1301},
  url = {https://doi.org/10.18653/v1/2026.findings-acl.1301}
}

References

51 references, 10 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015. Neural machine translation by jointly learning to align and translate. In Proc. ICLR’15.
  2. Pascal Bergsträßer, Ryan Cotterell, and Anthony W. Lin. 2025. Transformers are inherently succinct. CoRR, abs/2510.19315. — [arXiv:2510.19315](https://arxiv.org/abs/2510.19315) find
  3. Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. 2024. Separations in the Representational Capabilities of Transformers and Recurrent Architectures. In Advances of NeurIPS’24. find
  4. Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunsom. 2023. Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions. In Proc. ACL’23, pages 5767–5791. ACL. find
  5. Stella Biderman, Hailey Schoelkopf, Quentin Gregory Anthony, Herbie Bradley, Kyle O’Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, Aviya Skowron, Lintang Sutawika, and Oskar van der Wal. 2023. Pythia: A suite for analyzing large language models across… find
  6. Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter,… — Language Models are Few-Shot Learners
  7. Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014. Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation. In Proc. EMNLP’14, pages 1724–1734. ACL.
  8. Tri Dao and Albert Gu. 2024. Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality. In Proc. ICML’24, Proceedings of Machine Learning Research, pages 10041–10071. PMLR / OpenReview.net. find
  9. Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. 2019. Universal Transformers. In Proc. ICLR’19. OpenReview.net. find
  10. Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, and 6 others. 2021. A mathe… find
  11. Atticus Geiger, Hanson Lu, Thomas Icard, and Christopher Potts. 2021. Causal Abstractions of Neural Networks. In Advances of NeurIPS’21, pages 9574– 9586. find
  12. Robert Geirhos, Jörn-Henrik Jacobsen, Claudio Michaelis, Richard S. Zemel, Wieland Brendel, Matthias Bethge, and Felix A. Wichmann. 2020. Shortcut learning in deep neural networks. Nat. Mach. Intell., 2(11):665–673. find
  13. Riccardo Grazzi, Julien Siems, Arber Zela, Jörg K. H. Franke, Frank Hutter, and Massimiliano Pontil. 2025. Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues. In Proc. ICLR’25. OpenReview.net. find
  14. Albert Gu and Tri Dao. 2023. Mamba: Linear-time sequence modeling with selective state spaces. CoRR, abs/2312.00752. find
  15. Michael Hahn. 2020. Theoretical limitations of self-attention in neural sequence models. Trans. Assoc. Comput. Linguistics, 8:156–171. find
  16. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long Short-Term Memory. Neural Comput., 9(8):1735– 1780. find
  17. Samuel A. Korsky and Robert C. Berwick. 2019. On the Computational Power of RNNs. CoRR, abs/1906.06349. — [arXiv:1906.06349](https://arxiv.org/abs/1906.06349) find
  18. David Lindner, János Kramár, Sebastian Farquhar, Matthew Rahtz, Tom McGrath, and Vladimir Mikulik. 2023. Tracr: Compiled transformers as a laboratory for interpretability. In Advances of NeurIPS’23. find
  19. Jack Lindsey, Wes Gurnee, Emmanuel Ameisen, Brian Chen, Adam Pearce, Nicholas L. Turner, Craig Citro, David Abrahams, Shan Carter, Basil Hosmer, Jonathan Marcus, Michael Sklar, Adly Templeton, Trenton Bricken, Callum McDougall, Hoagy Cunningham, Thomas Henighan, Adam Jermyn, Andy Jones, and 8 others… find
  20. Ilya Loshchilov and Frank Hutter. 2019. Decoupled Weight Decay Regularization. In Proc. ICLR’19. OpenReview.net. find
  21. Shengjie Luo, Shanda Li, Shuxin Zheng, Tie-Yan Liu, Liwei Wang, and Di He. 2022. Your Transformer May Not be as Powerful as You Expect. In Advances of NeurIPS’22. find
  22. Maxime Méloux, Silviu Maniu, François Portet, and Maxime Peyrard. 2025. Everything, everywhere, all at once: Is mechanistic interpretability identifiable? In Proc. ICLR’25. OpenReview.net. find
  23. Kevin Meng, David Bau, Alex Andonian, and Yonatan Belinkov. 2022. Locating and editing factual associations in GPT. In Advances of NeurIPS’22. find
  24. William Merrill. 2019. Sequential Neural Networks as Automata. CoRR, abs/1906.01615. find
  25. William Merrill, Jackson Petty, and Ashish Sabharwal. 2024. The Illusion of State in State-Space Models. In Proc. ICML’24, Proceedings of Machine Learning Research, pages 35492–35506. PMLR / OpenReview.net. find
  26. William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav. 2020. A formal hierarchy of RNN architectures. In Proc. ACL’20, pages 443–459. ACL. find
  27. Tiberiu Musat. 2025. Mechanism and emergence of stacked attention heads in multi-layer transformers. In Proc. ICLR’25. OpenReview.net. find
  28. Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. 2020. Deep double descent: Where bigger models and more data hurt. In Proc. ICLR’20. OpenReview.net. find
  29. Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt. 2023. Progress measures for grokking via mechanistic interpretability. In Proc. ICLR’23. OpenReview.net.
  30. Swaroop Nath, Harshad Khadilkar, and Pushpak Bhattacharyya. 2024. Transformers are Expressive, But Are They Expressive Enough for Regression? CoRR, abs/2402.15478. — [arXiv:2402.15478](https://arxiv.org/abs/2402.15478) find
  31. Anil Nerode. 1958. Linear automaton transformations. Proceedings of the American Mathematical Society, 9(4):541–544. find
  32. Chris Olah, Nick Cammarata, Ludwig Schubert, Gabriel Goh, Michael Petrov, and Shan Carter. 2020. Zoom in: An introduction to circuits. Distill. find
  33. Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F. Christiano, Jan Leike, and Ryan Lowe. 2022.… — Training language models to follow instructions with human feedback
  34. Jorge Pérez, Pablo Barceló, and Javier Marinkovic. 2021. Attention is Turing-Complete. J. Mach. Learn. Res., 22:75:1–75:35. find
  35. Amir Pnueli. 1977. The temporal logic of programs. In Proc. FOCS’77, pages 46–57. IEEE Computer Society. find
  36. Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. 2022. Grokking: Generalization beyond overfitting on small algorithmic datasets. CoRR, abs/2201.02177.
  37. Clayton Sanford, Daniel J. Hsu, and Matus Telgarsky. 2023. Representational Strengths and Limitations of Transformers. In Advances of NeurIPS’23. find
  38. Yash Raj Sarrof, Yana Veitsman, and Michael Hahn. 2024. The Expressive Capacity of State Space Models: A Formal Language Perspective. In Advances of NeurIPS’24. find
  39. Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, and Praneeth Netrapalli. 2020. The pitfalls of simplicity bias in neural networks. In Advances of NeurIPS’20. find
  40. Peter Shaw, James Cohan, Jacob Eisenstein, and Kristina Toutanova. 2025. Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers. CoRR, abs/2509.22445. — [arXiv:2509.22445](https://arxiv.org/abs/2509.22445) find
  41. Hava T. Siegelmann and Eduardo D. Sontag. 1995. On the computational power of neural nets. J. Comput. Syst. Sci., 50(1):132–150. find
  42. Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. 2024. What formal languages can transformers express? A survey. Trans. Assoc. Comput. Linguistics, 12:543–561. find
  43. Jianlin Su, Murtadha H. M. Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. 2024. RoFormer: Enhanced transformer with Rotary Position Embedding. Neurocomputing, 568:127063.
  44. Vimal Thilak, Etai Littwin, Shuangfei Zhai, Omid Saremi, Roni Paiss, and Joshua M. Susskind. 2024. The Slingshot Effect: A Late-Stage Optimization Anomaly in Adaptive Gradient Methods. find
  45. Trans. Mach. Learn. Res., 2024. find
  46. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances of NeurIPS’17, pages 5998– 6008.
  47. Kevin Ro Wang, Alexandre Variengien, Arthur Conmy, Buck Shlegeris, and Jacob Steinhardt. 2023. Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 Small. In Proc. ICLR’23. OpenReview.net. find
  48. Gail Weiss, Yoav Goldberg, and Eran Yahav. 2018. On the Practical Computational Power of Finite Precision RNNs for Language Recognition. In Proc. ACL’18, pages 740–745. ACL.
  49. Gail Weiss, Yoav Goldberg, and Eran Yahav. 2021. Thinking like transformers. In Proc. ICML’21, volume 139 of Proceedings of Machine Learning Research, pages 11080–11090. PMLR. find
  50. Andy Yang, David Chiang, and Dana Angluin. 2024. Masked hard-attention transformers recognize exactly the star-free languages. In Advances of NeurIPS’24. find
  51. Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. 2020. Are transformers universal approximators of sequence-to-sequence functions? In Proc. ICLR’20. OpenReview.net.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zhao-2026-do-transformers-grok-succinct-algorithms/