# Logical Languages Accepted by Transformer Encoders with Hard Attention

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 22 references that are in the map.
- First posted on arXiv 5 Oct 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [Tighter Bounds on the Expressivity of Transformer Encoders](https://mlsanity.com/paper/2301.10743/) (2023)

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

- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages](https://mlsanity.com/paper/2310.13897/) (2023)
- [Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers](https://mlsanity.com/paper/2404.04393/) (2024)
- [A Theory of Learning with Autoregressive Chain of Thought](https://mlsanity.com/paper/2503.07932/) (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)
- [An Examination on the Effectiveness of Divide-and-Conquer Prompting in Large Language Models](https://mlsanity.com/paper/2402.05359/) (2024)
- [Knee-Deep in C-RASP: A Transformer Depth Hierarchy](https://mlsanity.com/paper/2506.16055/) (2025)
- [Unique Hard Attention: A Tale of Two Sides](https://mlsanity.com/paper/2503.14615/) (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)
- [Transformers as Transducers](https://mlsanity.com/paper/2404.02040/) (2024)
- [Ehrenfeucht-Haussler Rank and Chain of Thought](https://mlsanity.com/paper/2501.12997/) (2025)
- [The Transformer Cookbook](https://mlsanity.com/paper/2510.00368/) (2025)
- [Learning Linear Attention in Polynomial Time](https://mlsanity.com/paper/2410.10101/) (2024)
- [Parity, Sensitivity, and Transformers](https://mlsanity.com/paper/2602.05896/) (2026)
- [Transformers are Inherently Succinct](https://mlsanity.com/paper/2510.19315/) (2025)
- [Efficient Turing Machine Simulation with Transformers](https://mlsanity.com/paper/2512.00003/) (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)
- [A Transformer with Stack Attention](https://mlsanity.com/paper/2405.04515/) (2024)
- [Rosetta-PL: Propositional Logic as a Benchmark for Large Language Model Reasoning](https://mlsanity.com/paper/2505.00001/) (2025)
- [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 Existence of Universal Simulators of Attention](https://mlsanity.com/paper/2506.18739/) (2025)
- [From Neural Networks to Logical Theories: The Correspondence between Fibring Modal Logics and Fibring Neural Networks](https://mlsanity.com/paper/2509.23912/) (2025)
- [The Role of Logic and Automata in Understanding Transformers](https://mlsanity.com/paper/2509.24024/) (2025)
- [An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammars](https://mlsanity.com/paper/2606.17522/) (2026)
- [Comparison of different Unique hard attention transformer models by the formal languages they can recognize](https://mlsanity.com/paper/2506.03370/) (2025)

## Abstract (arXiv)

We contribute to the study of formal languages that can be recognized by transformer encoders. We focus on two self-attention mechanisms: (1) UHAT (Unique Hard Attention Transformers) and (2) AHAT (Average Hard Attention Transformers). UHAT encoders are known to recognize only languages inside the circuit complexity class sf AC0, i.e., accepted by a family of poly-sized and depth-bounded boolean circuits with unbounded fan-ins. On the other hand, AHAT encoders can recognize languages outside sf AC0), but their expressive power still lies within the bigger circuit complexity class sf TC0, i.e., sf AC0-circuits extended by majority gates. We first show a negative result that there is an sf AC0-language that cannot be recognized by an UHAT encoder. On the positive side, we show that UHAT encoders can recognize a rich fragment of sf AC0-languages, namely, all languages definable in first-order logic with arbitrary unary numerical predicates. This logic, includes, for example, all regular languages from sf AC0. We then show that AHAT encoders can recognize all languages of our logic even when we enrich it with counting terms. We apply these results to derive new results on the expressive power of UHAT and AHAT up to permutation of letters (a.k.a. Parikh images).