Research map / Architectures and efficiency / Attention and transformers
Characterizing the Expressivity of Fixed-Precision Transformer Language Models
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 fixed-precision soft-attention transformers with strict future masking and no positional encodings are exactly as expressive as the past-only LTL fragment PTL (equivalently PODFAs / left-deterministic polynomials), and validates this with length-generalization experiments.
Problem
Prior characterizations of transformer expressivity either assume unique hard attention or arbitrary/log precision; the exact expressivity of realistic fixed-precision soft-attention transformers (strict masking, NoPE) remained open.
Approach
Shows fixed-precision soft-attention transformers with strict masking and NoPE are exactly equivalent to PTL (past-only linear temporal logic) and to PODFAs; a construction handles vanishing attention weights by a two-layer past-of-conjunction trick without increasing precision.
Key results
- Transformers achieve 100% max accuracy on left-deterministic polynomial languages (PT-2, LT-1, LDP-2, LDP-1, FIRST) but at most 52-90% on languages outside the class, e.g., PARITY max 52.1%, DYCK-(1,2) max 83.4%.
- LSTMs reach 100% max accuracy on all tested languages, confirming learnability of the tasks.
- Transformer LM learns LDP-1 and LDP-2 with perfect per-token accuracy, while RDP-1 peaks at 98.3% and linear probes show intermixed state representations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a transformer instead of an LSTM for parity recognition | Language recognizer · parity | mean accuracy: 50.6\pm 0.8 vs. \mathbf{100.0}\pm 0.0 | Hurt |
| Use a transformer instead of an LSTM for cnt recognition | Language recognizer · cnt | mean accuracy: 53.6\pm 8.6 vs. 86.9\pm20.9 | Hurt |
| Use a transformer instead of an LSTM for dyck-(1,2) recognition | Language recognizer · dyck-(1,2) | mean accuracy: 64.2\pm8.0 vs. 99.3\pm1.0 | Hurt |
| Use a transformer instead of an LSTM for dyck-(1,1) recognition | Language recognizer · dyck-(1,1) | mean accuracy: 71.5\pm9.3 vs. 88.8\pm17.3 | Hurt |
| Use a transformer instead of an LSTM for lt-2 recognition | Language recognizer · lt-2 | mean accuracy: 57.9\pm2.3 vs. \mathbf{100.0}\pm0.0 | Hurt |
| Use a transformer instead of an LSTM for rdp-1 recognition | Language recognizer · rdp-1 | mean accuracy: 71.1\pm11.5 vs. \mathbf{100.0}\pm0.0 | Hurt |
| Use a transformer instead of an LSTM for last recognition | Language recognizer · last | mean accuracy: 57.3\pm2.7 vs. \mathbf{100.0}\pm0.0 | Hurt |
| Train a transformer on a left-deterministic polynomial language | Transformer · ldp-2 | mean accuracy: 100.0\pm0.0 | Helped |
| Train a transformer on a language outside its characterized capacity | Transformer · parity | mean accuracy: 50.6\pm 0.8 | Hurt |
| Train a transformer LM on rdp-1 rather than an ldp language | Transformer LM · rdp-1 | per-token accuracy: 98.3\% | Hurt |
| Train a transformer LM on ldp-1 | Transformer LM · ldp-1 | per-token accuracy: perfect accuracy | Helped |
Surprising findings
- Transformers fail to recognize simple languages such as bounded Dyck languages that are recognizable under more permissive idealizations.
- Transformer LM fails to reach 100% on RDP-1 because its non-partially-ordered DFA states are not linearly separable in representations.
Limitations
- Analysis restricted to NoPE, strict future masking, and single-head attention; positional encodings are deferred.
- Empirical validation uses small synthetic languages and length generalization up to 500 only.
- Under fixed precision the LM distribution may not be perfectly normalized.
Experimental setup
Datasets: synthetic formal languages (CNT, PARITY, DYCK, LT, RDP, LAST, PT, LDP, FIRST) with strings up to length 40, tested on 41
Benchmarks: synthetic formal language recognition (length generalization) per-token accuracy on RDP-1, LDP-2, LDP-1 language modeling
Metrics: accuracy (max and mean over seeds) per-token accuracy probing accuracy
Baselines: LSTM
Builds on: unique hard attention transformer characterization (LTL) C-RASP linear temporal logic first-order logic FO[2]
Closest papers by meaning
- Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages (NeurIPS 2024 · similarity 0.89)
- Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers (NeurIPS 2025 · similarity 0.88)
- Fixed Universal Transformers (NeurIPS 2026 · similarity 0.88)
- The Power of Hard Attention Transformers on Data Sequences: A formal language theoretic perspective (NeurIPS 2024 · similarity 0.88)
- Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning (ICLR 2025 · similarity 0.88)
- Beyond Components: Singular Vector-Based Interpretability of Transformer Circuits (NeurIPS 2025 · similarity 0.88)
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.