Research map / Architectures and efficiency / Attention and transformers
Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that masked hard-attention transformers with strict masking and no position embeddings recognize exactly the star-free languages (LTL), via an intermediate language Boolean RASP, and extends the characterization to position embeddings, non-strict masking, and depth.
Problem
Exact characterization of the formal languages recognized by transformers with hard attention and attention masking; prior work gave only upper or lower bounds.
Approach
Introduces Boolean RASP (B-RASP), a Boolean-valued restriction of RASP that compiles into masked hard-attention transformers and can be decompiled back, serving as an intermediate language to LTL so that known LTL results transfer to transformers.
Key results
- Masked hard-attention transformers with strict masking and no position embeddings recognize exactly the star-free languages (equivalent to LTL).
- With rational sinusoidal position embeddings, they recognize exactly the regular languages in AC^0.
- With arbitrary finite-image position embeddings, they are equivalent to LTL[Mon]; non-strict masking restricts them to stutter-invariant star-free languages.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use strict masking without position embeddings | Masked hard-attention transformers · Languages over Σ+ | expressive power | Mixed |
| Use strict masking instead of non-strict masking | Masked hard-attention transformers · Languages over Σ+ | expressive power | Helped |
| Use only future-masked rightmost-hard attention | Masked hard-attention transformers · Languages over Σ+ | expressive power | No clear effect |
| Add past-masked, non-masked, and/or leftmost-hard attention | Strictly masked hard-attention transformers · Languages over Σ+ | expressive power | No clear effect |
| Add rational sinusoidal position embeddings | Masked hard-attention transformers · Languages over Σ+ | expressive power | Helped |
| Add arbitrary finite-image position embeddings | Masked hard-attention transformers · Languages over Σ+ | expressive power | Helped |
| Add more self-attention layers | Masked hard-attention transformers · Languages over Σ+ | expressive power | Helped |
Surprising findings
- Non-strict masking reduces expressivity to only the stutter-invariant star-free languages.
- Only future-masked rightmost-hard attention is needed to recognize all star-free languages.
Limitations
- Results are for unique-hard attention, which differs from soft attention used in practice.
- Single-head attention in the main definition; multi-head and layer normalization handled as extensions.
- Characterization restricted to encoder-only acceptance at the last position.
Experimental setup
Baselines: hao-etal-2022-formal barcelo-etal-2023 perez-etal-2021-turing
Builds on: RASP LTL Krohn-Rhodes decomposition hao-etal-2022-formal
Closest papers by meaning
- Logical Languages Accepted by Transformer Encoders with Hard Attention (ICLR 2024 · similarity 0.91)
- Characterizing the Expressivity of Fixed-Precision Transformer Language Models (NeurIPS 2025 · similarity 0.89)
- The Power of Hard Attention Transformers on Data Sequences: A formal language theoretic perspective (NeurIPS 2024 · similarity 0.89)
- Strassen Attention, Split VC Dimension and Compositionality in Transformers (NeurIPS 2025 · similarity 0.87)
- Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers (NeurIPS 2025 · similarity 0.87)
- A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.