Research map / Architectures and efficiency / Attention and transformers
Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning
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 satisfiability of transformer encoders is undecidable in general (hardmax, expressive scoring, even with log-precision), decidable and NEXPTIME-bounded for bounded input length and for periodic-embedding or fixed-width quantized encoders, with NEXPTIME-hardness for fixed-width arithmetic.
Problem
Decidability and complexity of the satisfiability problem (trSat) for transformer encoders, which underlies formal verification and interpretation of transformers.
Approach
Reduces the unbounded octant tiling-word problem to trSat for a minimal transformer encoder class using hardmax normalisation and FNN scoring to show undecidability; then shows that bounded input length or fixed-width arithmetic with periodic embeddings yields decidability with NEXPTIME upper bounds (and NEXPTIME-hardness for fixed-width with arbitrary embeddings).
Key results
- trSat for the hardmax-based class T_udec is undecidable (Theorem 1), and remains undecidable for log-precision variant (Theorem 2).
- btrSat is NP-complete with unary and NEXPTIME-complete with binary input length bound when T_udec is included.
- trSat for additive-periodical TE over fixed-width arithmetic is in NEXPTIME, and trSat for fixed-width TE with arbitrary embeddings is decidable and NEXPTIME-hard.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use hardmax normalization with expressive scoring and positional embeddings | Transformer encoders in T_udec · Unbounded input | trSat decidability | Hurt |
| Restrict internal computation to log-precision | Transformer encoders in T_udec · Unbounded input | trSat decidability | No clear effect |
| Bound the input length | Transformer encoders in any computable class · Bounded input, unary n | decidability | Helped |
| Bound the input length and encode n in unary | Classes containing T_udec · Bounded input, unary n | complexity | Mixed |
| Bound the input length and encode n in binary | Classes containing T_udec · Bounded input, binary n | complexity | Mixed |
| Use an additive-periodical positional embedding and fixed-width arithmetic | Transformer encoders in T_fix_circle · Unbounded input | trSat decidability | Helped |
| Use fixed-width arithmetic while allowing arbitrary embeddings | Transformer encoders in T_fix · Unbounded input | trSat decidability | Helped |
| Use fixed-width arithmetic while allowing arbitrary embeddings | Transformer encoders in T_fix · Unbounded input | trSat complexity | Hurt |
Surprising findings
- Log-precision transformers remain undecidable for trSat, so log-precision alone does not enable formal reasoning.
- Fixed-width arithmetic makes trSat decidable despite the undecidability for real-valued encoders, but still NEXPTIME-hard.
Limitations
- Results rely on hardmax normalisation; unclear whether they hold for softmax.
- Decidability results only for TE classes at most as expressive as those considered; incomplete methods not covered.
- Assumes computability and polynomial-time evaluation of TE.
Experimental setup
Metrics: decidability complexity class membership
Builds on: log-precision transformers tiling problems
Closest papers by meaning
- Can Transformers Reason Logically? A Study in SAT Solving (ICML 2025 · similarity 0.91)
- The Expressive Power of Transformers with Chain of Thought (ICLR 2024 · similarity 0.90)
- Characterizing the Expressivity of Fixed-Precision Transformer Language Models (NeurIPS 2025 · similarity 0.88)
- Logical Languages Accepted by Transformer Encoders with Hard Attention (ICLR 2024 · similarity 0.87)
- Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (ICLR 2024 · similarity 0.87)
- Exact Expressive Power of Transformers with Padding (NeurIPS 2025 · similarity 0.87)
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.