Research map / Architectures and efficiency / Attention and transformers
Exact Expressive Power of Transformers with Padding
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 transformers with polynomial padding recognize exactly FO-uniform TC0, and that adding O(log^d n) looping yields exactly FO-uniform TC^d (hence FO-uniform NC with polylog looping), using complete-problem reductions.
Problem
Characterizing the exact expressive power of transformers when extended with inference-time padding tokens and looping, beyond the known TC0 upper bound and relative to parallelizable complexity classes.
Approach
Model padding as n^k extra positions storing all variable assignments so averaging-hard-attention transformers can evaluate FO+M2 (majority) formulas, and use complete problems under FO/L reductions with looping to reach TC^d for d>=1.
Key results
- Polynomially padded fixed-depth averaging-hard-attention transformers recognize exactly FO-uniform TC0 (uAHAT^0_* = AHAT^0_* = FO-uniform TC0).
- For d>=1, log^d-depth looped padded transformers recognize exactly FO-uniform TC^d (AHAT^d_* = FO-uniform TC^d).
- Polylog-looped poly-padded transformers recognize exactly FO-uniform NC.
- Proves uniformity collapse: FO-uniform TC^d = L-uniform TC^d = NL-uniform TC^d for d>=1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add polynomial padding to a fixed-depth AHAT | AHAT · Formal languages, fixed depth | expressive power | Helped |
| Add O(log^d n) looping to a polynomially padded AHAT | Polynomially padded AHAT · Formal languages, d ≥ 1 | expressive power | Helped |
| Use polylogarithmic looping with polynomial padding | AHAT · Formal languages, polylogarithmic looping | expressive power | Helped |
| Use logarithmic rather than polynomial precision | Polynomially padded AHAT · Formal languages, fixed depth | expressive power | No clear effect |
| Use logarithmic rather than polynomial precision | Polylog-looped, polynomially padded AHAT · Formal languages, polylogarithmic looping | expressive power | No clear effect |
Limitations
- Results assume idealized averaging-hard-attention with masked pre-norm rather than softmax attention.
- Unclear whether transformers can learn to use looped layers in practice.
- Padding extends context length, increasing memory overhead.
Experimental setup
Builds on: Pfau et al. padding tokens Merrill and Sabharwal transformer circuit bounds Universal transformers Chain-of-thought expressivity
Closest papers by meaning
- The Expressive Power of Transformers with Chain of Thought (ICLR 2024 · similarity 0.91)
- Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (ICLR 2024 · similarity 0.91)
- Distilling Sequential Computation in Transformer Language Models (NeurIPS 2026 · similarity 0.88)
- Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers (ICML 2025 · similarity 0.88)
- Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers (NeurIPS 2025 · similarity 0.88)
- On Expressive Power of Looped Transformers: Theoretical Analysis and Enhancement via Timestep Encoding (ICML 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.