mlsanityData to 14 Oct 2026

Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages

arXiv 2310.13897 ↗First posted 21 Oct 2023cs.FL cs.LG cs.LOcited by 49

Not on the map. Why?

Abstract (arXiv)

The expressive power of transformers over inputs of unbounded size can be studied through their ability to recognize classes of formal languages. In this paper, we establish exact characterizations of transformers with hard attention (in which all attention is focused on exactly one position) and attention masking (in which each position only attends to positions on one side). With strict masking (each position cannot attend to itself) and without position embeddings, these transformers are expressively equivalent to linear temporal logic (LTL), which defines exactly the star-free languages. A key technique is the use of Boolean RASP as a convenient intermediate language between transformers and LTL. We then take numerous results known for LTL and apply them to transformers, showing how position embeddings, strict masking, and depth all increase expressive power.

Key facts. Cited by 49 papers in the map (data through 14 Oct 2026). Builds on 16 of its 35 references that are in the map. First posted on arXiv 21 Oct 2023.

Builds on

16 of 35 references.

References · 16

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2020Language Models are Few-Shot Learnerscited by 32,419
  4. 2016Layer Normalizationcited by 5,669
  5. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  6. 2021Thinking Like Transformerscited by 184
  7. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 113
  8. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  9. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 93
  10. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 66
  11. 2021Memory-efficient Transformers via Top-k Attentioncited by 60
  12. 2020How Can Self-Attention Networks Recognize Dyck-n Languages?cited by 51
4 more
  1. 2023Learning Transformer Programscited by 41
  2. 2020Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descentcited by 40
  3. 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 38
  4. 2020Learning Hard Retrieval Decoder Attention for Transformerscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 8; 2025: 22; 2026: 19.

49 papers.

Sort:

By area:

  1. 2024Transformers, parallel computation, and logarithmic depthcited by 79
  2. 2024SynCode: LLM Generation with Grammar Augmentationcited by 69
  3. 2025Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biasescited by 37
  4. 2025Type-Constrained Code Generation with Language Modelscited by 35
  5. 2024Training Neural Networks as Recognizers of Formal Languagescited by 24
  6. 2025Exact Expressive Power of Transformers with Paddingcited by 19
  7. 2025Constant Bit-size Transformers Are Turing Completecited by 19
  8. 2024Simulating Hard Attention Using Soft Attentioncited by 15
  9. 2025Characterizing the Expressivity of Fixed-Precision Transformer Language Modelscited by 14
  10. 2025Knee-Deep in C-RASP: A Transformer Depth Hierarchycited by 12
  11. 2025Unique Hard Attention: A Tale of Two Sidescited by 10
  12. 2025The Counting Power of Transformerscited by 9
37 more
  1. 2024Transformers as Transducerscited by 8
  2. 2025Meta-Learning Neural Mechanisms rather than Bayesian Priorscited by 8
  3. 2025Ehrenfeucht-Haussler Rank and Chain of Thoughtcited by 6
  4. 2025The Transformer Cookbookcited by 6
  5. 2024Quantifying artificial intelligence through algorithmic generalizationcited by 5
  6. 2026Parity, Sensitivity, and Transformerscited by 5
  7. 2025Transformers are Inherently Succinctcited by 4
  8. 2025Efficient Turing Machine Simulation with Transformerscited by 4
  9. 2026Length Generalization Bounds for Transformerscited by 4
  10. 2025When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspectivecited by 3
  11. 2026Characterizing the Expressivity of Local Attention in Transformerscited by 3
  12. 2024Extracting Moore Machines from Transformers using Queries and Counterexamplescited by 2
  13. 2025Expressive Power of Graph Transformers via Logiccited by 2
  14. 2025From Next Token Prediction to (STRIPS) World Modelscited by 2
  15. 2025Probability Distributions Computed by Autoregressive Transformerscited by 2
  16. 2026On the Expressiveness of State Space Models via Temporal Logicscited by 2
  17. 2026On the Ability of Transformers to Verify Planscited by 2
  18. 2024Representing Rule-based Chatbots with Transformerscited by 1
  19. 2025Three tiers of computation in transformers and in brain architecturescited by 1
  20. 2025On the Existence of Universal Simulators of Attentioncited by 1
  21. 2025The Role of Logic and Automata in Understanding Transformerscited by 1
  22. 2026Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don'tcited by 1
  23. 2026An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammarscited by 1
  24. 2026Disentangling the Expressivity of RoPEcited by 1
  25. 2025Generative Linguistics, Large Language Models, and the Social Nature of Scientific Successcited by 0
  26. 2025Comparison of different Unique hard attention transformer models by the formal languages they can recognizecited by 0
  27. 2026Synthesis and Verification of Transformer Programs (Technical Report)cited by 0
  28. 2026Average Attention Transformers and Arithmetic Circuitscited by 0
  29. 2026Encoder-Decoder Transformers: Logical Characterizations and Periodicitycited by 0
  30. 2026Provably Shorter Scratchpads in Hybrid DeltaNet-Attention Decoderscited by 0
  31. 2026Causally Evaluating the Learnability of Formal Language Taskscited by 0
  32. 2026A Compositional Theory of Causally Masked Transformerscited by 0
  33. 2026On the Expressive Power of Transformerscited by 0
  34. 2026Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformerscited by 0
  35. 2026Latest Exact Match Attentioncited by 0
  36. 2026Hidden Reasoning Must Leak, but Need Not Be Readable: Fundamental Opportunities and Limits for Chain-of-Thought Monitoringcited by 0
  37. 2026Constraint-Aware Trainingcited by 0