# Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers

arXiv: https://arxiv.org/abs/2404.04393 · HTML: https://mlsanity.com/paper/2404.04393/

## 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 (most cited first, 13 of 13)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [Tracr: Compiled Transformers as a Laboratory for Interpretability](https://mlsanity.com/paper/2301.05062/) (2023)
- [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022)
- [Tighter Bounds on the Expressivity of Transformer Encoders](https://mlsanity.com/paper/2301.10743/) (2023)
- [Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descent](https://mlsanity.com/paper/2010.09697/) (2020)
- [Logical Languages Accepted by Transformer Encoders with Hard Attention](https://mlsanity.com/paper/2310.03817/) (2023)
- [On the Expressivity Role of LayerNorm in Transformers' Attention](https://mlsanity.com/paper/2305.02582/) (2023)

## Built on by (most cited first, 30 of 39)

- [The Expressive Capacity of State Space Models: A Formal Language Perspective](https://mlsanity.com/paper/2405.17394/) (2024)
- [Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biases](https://mlsanity.com/paper/2502.19249/) (2025)
- [PENCIL: Long Thoughts with Short Memory](https://mlsanity.com/paper/2503.14337/) (2025)
- [Language Models Need Inductive Biases to Count Inductively](https://mlsanity.com/paper/2405.20131/) (2024)
- [The Geometry of Reasoning: Flowing Logics in Representation Space](https://mlsanity.com/paper/2510.09782/) (2025)
- [Exact Expressive Power of Transformers with Padding](https://mlsanity.com/paper/2505.18948/) (2025)
- [Simulating Hard Attention Using Soft Attention](https://mlsanity.com/paper/2412.09925/) (2024)
- [Characterizing the Expressivity of Fixed-Precision Transformer Language Models](https://mlsanity.com/paper/2505.23623/) (2025)
- [Knee-Deep in C-RASP: A Transformer Depth Hierarchy](https://mlsanity.com/paper/2506.16055/) (2025)
- [The Counting Power of Transformers](https://mlsanity.com/paper/2505.11199/) (2025)
- [Softmax Transformers are Turing-Complete](https://mlsanity.com/paper/2511.20038/) (2025)
- [Meta-Learning Neural Mechanisms rather than Bayesian Priors](https://mlsanity.com/paper/2503.16048/) (2025)
- [Quantitative Bounds for Length Generalization in Transformers](https://mlsanity.com/paper/2510.27015/) (2025)
- [ALTA: Compiler-Based Analysis of Transformers](https://mlsanity.com/paper/2410.18077/) (2024)
- [Ehrenfeucht-Haussler Rank and Chain of Thought](https://mlsanity.com/paper/2501.12997/) (2025)
- [Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilities](https://mlsanity.com/paper/2505.21785/) (2025)
- [The Transformer Cookbook](https://mlsanity.com/paper/2510.00368/) (2025)
- [Context-Free Recognition with Transformers](https://mlsanity.com/paper/2601.01754/) (2026)
- [Length Generalization Bounds for Transformers](https://mlsanity.com/paper/2603.02238/) (2026)
- [The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics](https://mlsanity.com/paper/2505.11930/) (2025)
- [Probability Distributions Computed by Autoregressive Transformers](https://mlsanity.com/paper/2510.27118/) (2025)
- [On the Expressiveness of State Space Models via Temporal Logics](https://mlsanity.com/paper/2601.19467/) (2026)
- [On the Ability of Transformers to Verify Plans](https://mlsanity.com/paper/2603.19954/) (2026)
- [Tracr-Injection: Distilling Algorithms into Pre-trained Language Models](https://mlsanity.com/paper/2505.10719/) (2025)
- [On the Existence of Universal Simulators of Attention](https://mlsanity.com/paper/2506.18739/) (2025)
- [The Role of Logic and Automata in Understanding Transformers](https://mlsanity.com/paper/2509.24024/) (2025)
- [A model of errors in transformers](https://mlsanity.com/paper/2601.14175/) (2026)
- [Barriers to Universal Reasoning With Transformers (And How to Overcome Them)](https://mlsanity.com/paper/2604.25800/) (2026)
- [Language Acquisition Device in Large Language Models](https://mlsanity.com/paper/2605.16758/) (2026)
- [Positional versus Symbolic Attention Heads: Learning Dynamics, RoPE Geometry, and Length Generalization](https://mlsanity.com/paper/2605.31558/) (2026)

## 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.