# Tighter Bounds on the Expressivity of Transformer Encoders

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

## Key facts

- Cited by 66 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 32 references that are in the map.
- First posted on arXiv 25 Jan 2023.

## Builds on (most cited first, 16 of 16)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Learning Deep Transformer Models for Machine Translation](https://mlsanity.com/paper/1906.01787/) (2019)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Transformers without Tears: Improving the Normalization of Self-Attention](https://mlsanity.com/paper/1910.05895/) (2019)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Tracr: Compiled Transformers as a Laboratory for Interpretability](https://mlsanity.com/paper/2301.05062/) (2023)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [Recurrent Neural Networks as Weighted Language Recognizers](https://mlsanity.com/paper/1711.05408/) (2017)
- [On the Linguistic Capacity of Real-Time Counter Automata](https://mlsanity.com/paper/2004.06866/) (2020)
- [SoPa: Bridging CNNs, RNNs, and Weighted Finite-State Machines](https://mlsanity.com/paper/1805.06061/) (2018)

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

- [Large Language Models](https://mlsanity.com/paper/2307.05782/) (2023)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [Repeat After Me: Transformers are Better than State Space Models at Copying](https://mlsanity.com/paper/2402.01032/) (2024)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Why are Sensitive Functions Hard for Transformers?](https://mlsanity.com/paper/2402.09963/) (2024)
- [A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers](https://mlsanity.com/paper/2503.03961/) (2025)
- [The Expressive Power of Transformers with Chain of Thought](https://mlsanity.com/paper/2310.07923/) (2023)
- [Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages](https://mlsanity.com/paper/2310.13897/) (2023)
- [The Expressive Capacity of State Space Models: A Formal Language Perspective](https://mlsanity.com/paper/2405.17394/) (2024)
- [Transformers are Universal In-context Learners](https://mlsanity.com/paper/2408.01367/) (2024)
- [Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers](https://mlsanity.com/paper/2404.04393/) (2024)
- [Logical Languages Accepted by Transformer Encoders with Hard Attention](https://mlsanity.com/paper/2310.03817/) (2023)
- [Transformers Can Represent n-gram Language Models](https://mlsanity.com/paper/2404.14994/) (2024)
- [Separations in the Representational Capabilities of Transformers and Recurrent Architectures](https://mlsanity.com/paper/2406.09347/) (2024)
- [Measure-to-measure interpolation using Transformers](https://mlsanity.com/paper/2411.04551/) (2024)
- [The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity](https://mlsanity.com/paper/2412.06148/) (2024)
- [Exact Expressive Power of Transformers with Padding](https://mlsanity.com/paper/2505.18948/) (2025)
- [Do pretrained Transformers Learn In-Context by Gradient Descent?](https://mlsanity.com/paper/2310.08540/) (2023)
- [Characterizing the Expressivity of Fixed-Precision Transformer Language Models](https://mlsanity.com/paper/2505.23623/) (2025)
- [An Examination on the Effectiveness of Divide-and-Conquer Prompting in Large Language Models](https://mlsanity.com/paper/2402.05359/) (2024)
- [Ask, and it shall be given: On the Turing completeness of prompting](https://mlsanity.com/paper/2411.01992/) (2024)
- [Unique Hard Attention: A Tale of Two Sides](https://mlsanity.com/paper/2503.14615/) (2025)
- [ALTA: Compiler-Based Analysis of Transformers](https://mlsanity.com/paper/2410.18077/) (2024)
- [Strong hallucinations from negation and how to fix them](https://mlsanity.com/paper/2402.10543/) (2024)
- [Transformers are Expressive, But Are They Expressive Enough for Regression?](https://mlsanity.com/paper/2402.15478/) (2024)
- [Ehrenfeucht-Haussler Rank and Chain of Thought](https://mlsanity.com/paper/2501.12997/) (2025)
- [Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers](https://mlsanity.com/paper/2509.22445/) (2025)
- [Transformers through the lens of support-preserving maps between measures](https://mlsanity.com/paper/2509.25611/) (2025)

## Abstract (arXiv)

Characterizing neural networks in terms of better-understood formal systems has the potential to yield new insights into the power and limitations of these networks. Doing so for transformers remains an active area of research. Bhattamishra and others have shown that transformer encoders are at least as expressive as a certain kind of counter machine, while Merrill and Sabharwal have shown that fixed-precision transformer encoders recognize only languages in uniform TC0. We connect and strengthen these results by identifying a variant of first-order logic with counting quantifiers that is simultaneously an upper bound for fixed-precision transformer encoders and a lower bound for transformer encoders. This brings us much closer than before to an exact characterization of the languages that transformer encoders recognize.