Research map / Architectures and efficiency / Attention and transformers
The Power of Hard Attention Transformers on Data Sequences: A formal language theoretic perspective
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.
Studies expressive power of unique hard attention transformer encoders over data sequences (tuples of rationals), showing they go beyond AC0 (within TC0), can recognize a non-regular language without positional encoding, and capture an LTL extension with locally testable arithmetic.
Problem
Formal language theory of transformer encoders assumes a finite alphabet with token embeddings, which does not cover time series or arbitrary numeric inputs; the expressive power of transformers on sequences of numbers is unknown.
Approach
Extends UHAT analysis to infinite alphabets Q^d: shows UHAT with positional encodings lie in TC0 (not AC0) via polynomial constraints and rational approximation, gives a non-regular UHAT language without positional encodings, and shows an LTL extension with unary numeric predicates and local arithmetic tests is captured by UHAT.
Key results
- UHAT with positional encoding over data sequences lie in TC0 but not AC0 (a TC0-hard language is accepted by UHAT without positional encoding).
- A non-regular language Double (each number more than twice the previous) is accepted by past-masked UHAT without positional encoding.
- Every LTL^{lt}-definable language is accepted by UHAT with positional encoding, including moving-average and linear recurrence sequence properties.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use arbitrary data-sequence inputs instead of strings over a finite alphabet | UHAT · Circuit complexity | circuit complexity class: AC^0 -> TC^0 | Helped |
| Use data-sequence inputs without positional encodings | UHAT · Data sequences over Q^d | language class: regular -> non-regular | Helped |
| Add positional encoding | UHAT on data sequences · LTL-definable languages | language recognition | Helped |
Surprising findings
- Over data sequences, UHAT without positional encodings already escape AC0 and regularity, in contrast to finite alphabets.
- Real-valued constants cannot in general be replaced by rationals without changing behavior even on very short inputs, so rational approximation alone does not suffice.
Limitations
- Real constants and unbounded precision are idealized; uniformity of TC0 bound requires rational constants and computable positional encodings.
- Logic LTL^{lt} does not capture full UHAT expressivity (e.g., palindromes not covered by the logic).
- Results are purely theoretical with no experiments.
Experimental setup
Builds on: UHAT formal analysis over finite alphabets LTL with unary numeric predicates symbolic automata
Closest papers by meaning
- Logical Languages Accepted by Transformer Encoders with Hard Attention (ICLR 2024 · similarity 0.90)
- Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages (NeurIPS 2024 · similarity 0.89)
- Characterizing the Expressivity of Fixed-Precision Transformer Language Models (NeurIPS 2025 · similarity 0.88)
- Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modeling (NeurIPS 2024 · similarity 0.87)
- Distilling Sequential Computation in Transformer Language Models (NeurIPS 2026 · similarity 0.86)
- Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (ICLR 2024 · 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.