Do Transformers Grok Succinct Algorithms? Mechanistic Evidence for Counting Circuits

摘要

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.