@inproceedings{zhao-2026-transformers,
title = "Do Transformers Grok Succinct Algorithms? Mechanistic Evidence for Counting Circuits",
author = "Zhao, Yizheng",
editor = "Liakata, Maria and
Moreira, Viviane P. and
Zhang, Jiajun and
Jurgens, David",
booktitle = "Findings of the {A}ssociation for {C}omputational {L}inguistics: {ACL} 2026",
month = jul,
year = "2026",
address = "San Diego, California, United States",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/2026.findings-acl.1301/",
doi = "10.18653/v1/2026.findings-acl.1301",
pages = "26114--26130",
ISBN = "979-8-89176-395-1",
abstract = "Recent theory suggests Transformers are inherently succinct, capable of representing recursive algorithms like binary counting over exponential state spaces using constant-size circuits, unlike the exponential bottleneck of RNNs. However, it remains unclear under what conditions gradient-trained Transformers converge to these predicted succinct circuits, or whether they settle for heuristics. We bridge this gap by rigorously testing the Succinctness Hypothesis via mechanistic interpretability on the LargeCounter task. We report a striking dichotomy: shallow Transformers ($d=64$) generalize perfectly, whereas massive LSTM baselines ($d=2048$) fail completely ($<6\%$ accuracy), empirically validating the succinctness gap. This dichotomy extends to modern state-space models: Mamba and Mamba-2 fail even more catastrophically ($<1.1\%$), confirming the hierarchy Transformer $\gg$ LSTM $>$ SSM predicted by formal complexity results. We show this capability is acquired via a grokking phase transition driven by a weight-norm ``complexity collapse''. Mechanistic analysis reveals the learned circuit aligns precisely with Boolean RASP theory: attention heads utilize Rotary Positional Embeddings (RoPE) for ``Same-Bit Lookup'', while MLPs act as exact XOR/AND logic gates. Furthermore, we detect analogous ``Arithmetic Heads'' in pre-trained LLMs (Pythia), suggesting that succinctness is a representational inductive bias that, when activated by sufficient regularization, governs how models learn algorithmic reasoning."
}<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="zhao-2026-transformers">
<titleInfo>
<title>Do Transformers Grok Succinct Algorithms? Mechanistic Evidence for Counting Circuits</title>
</titleInfo>
<name type="personal">
<namePart type="given">Yizheng</namePart>
<namePart type="family">Zhao</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2026-07</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Findings of the Association for Computational Linguistics: ACL 2026</title>
</titleInfo>
<name type="personal">
<namePart type="given">Maria</namePart>
<namePart type="family">Liakata</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Viviane</namePart>
<namePart type="given">P</namePart>
<namePart type="family">Moreira</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Jiajun</namePart>
<namePart type="family">Zhang</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">David</namePart>
<namePart type="family">Jurgens</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">San Diego, California, United States</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
<identifier type="isbn">979-8-89176-395-1</identifier>
</relatedItem>
<abstract>Recent theory suggests Transformers are inherently succinct, capable of representing recursive algorithms like binary counting over exponential state spaces using constant-size circuits, unlike the exponential bottleneck of RNNs. However, it remains unclear under what conditions gradient-trained Transformers converge to these predicted succinct circuits, or whether they settle for heuristics. We bridge this gap by rigorously testing the Succinctness Hypothesis via mechanistic interpretability on the LargeCounter task. We report a striking dichotomy: shallow Transformers (d=64) generalize perfectly, whereas massive LSTM baselines (d=2048) fail completely (<6% accuracy), empirically validating the succinctness gap. This dichotomy extends to modern state-space models: Mamba and Mamba-2 fail even more catastrophically (<1.1%), confirming the hierarchy Transformer \gg LSTM > SSM predicted by formal complexity results. We show this capability is acquired via a grokking phase transition driven by a weight-norm “complexity collapse”. Mechanistic analysis reveals the learned circuit aligns precisely with Boolean RASP theory: attention heads utilize Rotary Positional Embeddings (RoPE) for “Same-Bit Lookup”, while MLPs act as exact XOR/AND logic gates. Furthermore, we detect analogous “Arithmetic Heads” in pre-trained LLMs (Pythia), suggesting that succinctness is a representational inductive bias that, when activated by sufficient regularization, governs how models learn algorithmic reasoning.</abstract>
<identifier type="citekey">zhao-2026-transformers</identifier>
<identifier type="doi">10.18653/v1/2026.findings-acl.1301</identifier>
<location>
<url>https://aclanthology.org/2026.findings-acl.1301/</url>
</location>
<part>
<date>2026-07</date>
<extent unit="page">
<start>26114</start>
<end>26130</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings
%T Do Transformers Grok Succinct Algorithms? Mechanistic Evidence for Counting Circuits
%A Zhao, Yizheng
%Y Liakata, Maria
%Y Moreira, Viviane P.
%Y Zhang, Jiajun
%Y Jurgens, David
%S Findings of the Association for Computational Linguistics: ACL 2026
%D 2026
%8 July
%I Association for Computational Linguistics
%C San Diego, California, United States
%@ 979-8-89176-395-1
%F zhao-2026-transformers
%X Recent theory suggests Transformers are inherently succinct, capable of representing recursive algorithms like binary counting over exponential state spaces using constant-size circuits, unlike the exponential bottleneck of RNNs. However, it remains unclear under what conditions gradient-trained Transformers converge to these predicted succinct circuits, or whether they settle for heuristics. We bridge this gap by rigorously testing the Succinctness Hypothesis via mechanistic interpretability on the LargeCounter task. We report a striking dichotomy: shallow Transformers (d=64) generalize perfectly, whereas massive LSTM baselines (d=2048) fail completely (<6% accuracy), empirically validating the succinctness gap. This dichotomy extends to modern state-space models: Mamba and Mamba-2 fail even more catastrophically (<1.1%), confirming the hierarchy Transformer \gg LSTM > SSM predicted by formal complexity results. We show this capability is acquired via a grokking phase transition driven by a weight-norm “complexity collapse”. Mechanistic analysis reveals the learned circuit aligns precisely with Boolean RASP theory: attention heads utilize Rotary Positional Embeddings (RoPE) for “Same-Bit Lookup”, while MLPs act as exact XOR/AND logic gates. Furthermore, we detect analogous “Arithmetic Heads” in pre-trained LLMs (Pythia), suggesting that succinctness is a representational inductive bias that, when activated by sufficient regularization, governs how models learn algorithmic reasoning.
%R 10.18653/v1/2026.findings-acl.1301
%U https://aclanthology.org/2026.findings-acl.1301/
%U https://doi.org/10.18653/v1/2026.findings-acl.1301
%P 26114-26130
Markdown (Informal)
[Do Transformers Grok Succinct Algorithms? Mechanistic Evidence for Counting Circuits](https://aclanthology.org/2026.findings-acl.1301/) (Zhao, Findings 2026)
ACL