mlsanityData to 14 Oct 2026

Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers

arXiv 2404.04393 ↗First posted 5 Apr 2024cs.LO cs.CL cs.FLcited by 39

Not on the map. Why?

Abstract (arXiv)

Deriving formal bounds on the expressivity of transformers, as well as studying transformers that are constructed to implement known algorithms, are both effective methods for better understanding the computational power of transformers. Towards both ends, we introduce the temporal counting logic textsfKt[#] alongside the RASP variant textsfC-RASP. We show they are equivalent to each other, and that together they are the best-known lower bound on the formal expressivity of future-masked soft attention transformers with unbounded input size. We prove this by showing all textsfKt[#] formulas can be compiled into these transformers.

Key facts. Cited by 39 papers in the map (data through 14 Oct 2026). Builds on 13 of its 30 references that are in the map. First posted on arXiv 5 Apr 2024.

Builds on

13 of 30 references.

References · 13

  1. 2017Attention Is All You Needcited by 60,361
  2. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 503
  3. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 257
  4. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 199
  5. 2021Thinking Like Transformerscited by 184
  6. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  7. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  8. 2023Tracr: Compiled Transformers as a Laboratory for Interpretabilitycited by 104
  9. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  10. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 66
  11. 2020Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descentcited by 40
  12. 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 38
1 more
  1. 2023On the Expressivity Role of LayerNorm in Transformers' Attentioncited by 33

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 4; 2025: 19; 2026: 16.

39 papers.

Sort:

By area:

  1. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 46
  2. 2025Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biasescited by 37
  3. 2025PENCIL: Long Thoughts with Short Memorycited by 33
  4. 2024Language Models Need Inductive Biases to Count Inductivelycited by 25
  5. 2025The Geometry of Reasoning: Flowing Logics in Representation Spacecited by 21
  6. 2025Exact Expressive Power of Transformers with Paddingcited by 19
  7. 2024Simulating Hard Attention Using Soft Attentioncited by 15
  8. 2025Characterizing the Expressivity of Fixed-Precision Transformer Language Modelscited by 14
  9. 2025Knee-Deep in C-RASP: A Transformer Depth Hierarchycited by 12
  10. 2025The Counting Power of Transformerscited by 9
  11. 2025Softmax Transformers are Turing-Completecited by 9
  12. 2025Meta-Learning Neural Mechanisms rather than Bayesian Priorscited by 8
27 more
  1. 2025Quantitative Bounds for Length Generalization in Transformerscited by 8
  2. 2024ALTA: Compiler-Based Analysis of Transformerscited by 7
  3. 2025Ehrenfeucht-Haussler Rank and Chain of Thoughtcited by 6
  4. 2025Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilitiescited by 6
  5. 2025The Transformer Cookbookcited by 6
  6. 2026Context-Free Recognition with Transformerscited by 4
  7. 2026Length Generalization Bounds for Transformerscited by 4
  8. 2025The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logicscited by 2
  9. 2025Probability Distributions Computed by Autoregressive Transformerscited by 2
  10. 2026On the Expressiveness of State Space Models via Temporal Logicscited by 2
  11. 2026On the Ability of Transformers to Verify Planscited by 2
  12. 2025Tracr-Injection: Distilling Algorithms into Pre-trained Language Modelscited by 1
  13. 2025On the Existence of Universal Simulators of Attentioncited by 1
  14. 2025The Role of Logic and Automata in Understanding Transformerscited by 1
  15. 2026A model of errors in transformerscited by 1
  16. 2026Barriers to Universal Reasoning With Transformers (And How to Overcome Them)cited by 1
  17. 2026Language Acquisition Device in Large Language Modelscited by 1
  18. 2026Positional versus Symbolic Attention Heads: Learning Dynamics, RoPE Geometry, and Length Generalizationcited by 1
  19. 2026Disentangling the Expressivity of RoPEcited by 1
  20. 2025Post-Norm can Resharpen Attentioncited by 0
  21. 2026Synthesis and Verification of Transformer Programs (Technical Report)cited by 0
  22. 2026Encoder-Decoder Transformers: Logical Characterizations and Periodicitycited by 0
  23. 2026Provably Shorter Scratchpads in Hybrid DeltaNet-Attention Decoderscited by 0
  24. 2026Rubato: Transcribing Piano Music with Timestampscited by 0
  25. 2026From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASPcited by 0
  26. 2026Hierarchical Domain Generalizationcited by 0
  27. 2026Length Generalization for Transformers via Compressioncited by 0