Pith. sign in

REVIEW 26 cited by

Transformers Learn Shortcuts to Automata

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2210.10749 v2 pith:I6CXHCOX submitted 2022-10-19 cs.LG cs.FLstat.ML

Bingbin Liu , Jordan T. Ash , Surbhi Goel , Akshay Krishnamurthy , Cyril Zhang This is my paper · ORCID
classification cs.LGcs.FLstat.ML
keywords solutionsmodelsreasoningtransformerautomataautomatoncomputationdepth
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

Algorithmic reasoning requires capabilities which are most naturally understood through recurrent models of computation, like the Turing machine. However, Transformer models, while lacking recurrence, are able to perform such reasoning using far fewer layers than the number of reasoning steps. This raises the question: what solutions are learned by these shallow and non-recurrent models? We find that a low-depth Transformer can represent the computations of any finite-state automaton (thus, any bounded-memory algorithm), by hierarchically reparameterizing its recurrent dynamics. Our theoretical results characterize shortcut solutions, whereby a Transformer with $o(T)$ layers can exactly replicate the computation of an automaton on an input sequence of length $T$. We find that polynomial-sized $O(\log T)$-depth solutions always exist; furthermore, $O(1)$-depth simulators are surprisingly common, and can be understood using tools from Krohn-Rhodes theory and circuit complexity. Empirically, we perform synthetic experiments by training Transformers to simulate a wide variety of automata, and show that shortcut solutions can be learned via standard training. We further investigate the brittleness of these solutions and propose potential mitigations.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 26 Pith papers

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

  1. On the Emergence of Implicit Curriculum in RLVR Learning Dynamics

    cs.LG 2026-02 unverdicted novelty 8.0 of 10

    RLVR training on transformers for compositional tasks follows an implicit curriculum from easy to hard problems, with difficulty spectrum smoothness determining steady relay progress or grokking phase transitions.

  2. A First-Principles Theory of Slow Thinking and Active Perception

    cs.AI 2026-07 conditional novelty 7.5 of 10

    Active lifting of data distributions via latent-sequence sampling and max-rate uncertainty reduction formally derives slow-thinking LLMs and places them on representation and sampler hierarchies that can be climbed.

  3. Attention-based representations for multi-task computation

    cs.LG 2026-08 accept novelty 7.0 of 10

    For min/max readout, two attention heads beat one head by an exponential resource gap, and for n-bit parity and symmetric Boolean functions, heads times polynomial degree must reach the threshold degree, with matching...

  4. When Does Reward Teach State? A Hidden-Automaton Instrument and a Group-Language Warning Signal

    cs.LG 2026-07 conditional novelty 7.0 of 10

    High reward in sparse RL does not imply latent-state recovery; a hidden-DFA instrument separates perception from planning gaps and flags group-language structure as a pre-training warning.

  5. Learning State-Tracking from Code Using Linear RNNs

    cs.LG 2026-02 unverdicted novelty 7.0 of 10

    Linear RNNs with negative eigenvalues track permutation state from REPL traces under next-token prediction, but probabilistic state-tracking with partial reveals forces exponential belief decay without nonlinear renor...

  6. Context-Free Recognition with Transformers

    cs.LG 2026-01 conditional novelty 7.0 of 10

    Looped transformers with O(log n) layer repetitions and O(n^6) padding tokens can recognize all context-free languages; unambiguous and unambiguous-linear subclasses need only O(n^3) and O(n^2) padding.

  7. Scaling Latent Reasoning via Looped Language Models

    cs.CL 2025-10 unverdicted novelty 7.0 of 10

    Looped language models with latent iterative computation and entropy-regularized depth allocation achieve performance matching up to 12B standard LLMs through superior knowledge manipulation.

  8. Too Long, Didn't Model: Decomposing LLM Long-Context Understanding With Novels

    cs.CL 2025-05 conditional novelty 7.0 of 10

    None of the seven frontier LLMs tested retain stable performance on novel-level summary, storyworld, and narrative-time tasks once input length exceeds roughly 64k tokens, despite advertised context windows up to 10M tokens.

  9. ICLR: In-Context Learning of Representations

    cs.CL 2024-12 conditional novelty 7.0 of 10

    As in-context examples grow, Llama-3.1-8B reorganizes its concept representations to mirror the connectivity structure of a graph defined entirely in context.

  10. Neural Scaling Laws Rooted in the Data Distribution

    cs.LG 2024-12 conditional novelty 7.0 of 10

    Percolation theory at criticality produces a Zipf distribution of subtasks, from which the paper derives neural scaling laws with alpha=1 quanta and a data-scaling exponent of 0.5.

  11. Hierarchical Domain Generalization

    cs.LG 2026-07 conditional novelty 6.0 of 10

    Over infinite domains, hierarchy-uniform domain generalization is impossible for every nontrivial hypothesis class; a length-generalization bound is a property of the length hierarchy, not a hierarchy-free guarantee.

  12. Pretraining Recurrent Networks without Recurrence

    cs.LG 2026-06 unverdicted novelty 6.0 of 10

    SMT trains nonlinear RNNs by imitating one-step memory-transition labels generated by a Transformer, replacing BPTT's unrolled credit assignment with time-parallel supervised learning.

  13. Rethinking Memorization Measures and their Implications in Large Language Models

    cs.LG 2025-07 conditional novelty 6.0 of 10

    Contextual memorization, defined by comparing a string's training loss against the best loss without training on that string, is stricter than counterfactual memorization and suggests that zero-memorization optimal le...

  14. Sample Complexity and Representation Ability of Test-time Scaling Paradigms

    cs.LG 2025-06 conditional novelty 6.0 of 10

    Best-of-n sampling provably needs about 1/Δ samples versus 1/Δ² for self-consistency, and a constructed Transformer can route among experts using verifier feedback to reach near-optimal final responses.

  15. Transformers Meet In-Context Learning: A Universal Approximation Theory

    cs.LG 2025-06 accept novelty 6.0 of 10

    A constructive theorem shows that transformers can perform in-context learning for any Barron-type function class by combining universal features with an emulated Lasso solver.

  16. Transformers as Multi-task Learners: Decoupling Features in Hidden Markov Models

    cs.LG 2025-06 conditional novelty 6.0 of 10

    A hand-constructed O(ln L + T)-layer Transformer is shown to approximate low-rank hidden Markov models in-context, with lower layers extracting local history features and upper layers performing regression-based decoding.

  17. Transformers versus the EM Algorithm in Multi-class Clustering

    stat.ML 2025-02 conditional novelty 6.0 of 10

    A pretrained transformer can approximate Lloyd's EM algorithm for multi-class Gaussian clustering and can achieve the minimax optimal clustering error with enough pretraining data.

  18. Learning Spectral Methods by Transformers

    stat.ML 2025-01 conditional novelty 6.0 of 10

    Pre-trained Transformers can provably approximate spectral methods (PCA and two-class Gaussian clustering) when trained on many instances, with bounds that decay as sample size grows.

  19. Rethinking Addressing in Language Models via Contexualized Equivariant Positional Encoding

    cs.CL 2025-01 conditional novelty 6.0 of 10

    TAPE makes positional embeddings content-aware and equivariant, improving Transformer performance on arithmetic and long-context tasks and extending representational power to NC1-complete algorithms.

  20. A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions: Representation, Training, Generalization

    cs.LG 2025-06 conditional novelty 5.0 of 10

    Single-layer linear self-attention can represent, train on, and length-generalize pairwise interaction functions under data-versatility and exact-realizability assumptions, and the paper introduces higher-order HyperA...

  21. Revisiting Test-Time Scaling: A Survey and a Diversity-Aware Method for Efficient Reasoning

    cs.CL 2025-06 conditional novelty 5.0 of 10

    ADAPT, a diversity-aware prefix fine-tuning method, improves best-of-N sampling efficiency for a 1.5B reasoning model, reaching 80% accuracy at N=32 versus N=256 for the baseline.

  22. An Analysis for Reasoning Bias of Language Models with Small Initialization

    cs.CL 2025-02 conditional novelty 5.0 of 10

    Initialization scale controls whether a transformer learns compositional reasoning or memorized mappings, because reasoning tokens acquire more differentiated embeddings early in training.

  23. The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity

    cs.CC 2024-12 conditional novelty 5.0 of 10

    Mamba and state-space models with constant depth and poly(n) precision are shown to lie in DLOGTIME-uniform TC0, the same circuit class as Transformers, so their expressiveness is bounded unless TC0=NC1.

  24. Naju: A Native Discrete State-Space Model with Independent Retention and Writing for Long-Sequence Memory

    cs.AI 2026-07 conditional novelty 4.0 of 10

    Decoupling the forget gate from the input gate in a discrete state-space recurrence lets one fixed-size state both preserve old bindings over long horizons and overwrite stale ones.

  25. Position: A Theory of Deep Learning Must Include Compositional Sparsity

    cs.LG 2025-07 conditional novelty 4.0 of 10

    All polynomial-time computable functions are compositionally sparse, and this property is the proposed reason deep networks avoid the curse of dimensionality and achieve practical success.

  26. Circuit Complexity Bounds for Visual Autoregressive Model

    stat.ML 2025-01 reject novelty 4.0 of 10

    The authors show that a simplified formalization of the VAR image generation model lies in DLOGTIME-uniform TC0, meaning it can be simulated by constant-depth threshold circuits with polynomial size and precision.

Pith tools