# Exact Expressive Power of Transformers with Padding arXiv: https://arxiv.org/abs/2505.18948 ยท HTML: https://mlsanity.com/paper/2505.18948/ ## Key facts - Cited by 19 papers in the map (data through 14 Oct 2026). - Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. - Builds on 20 of its 34 references that are in the map. - First posted on arXiv 25 May 2025. ## Placed in - LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/) ## Builds on (most cited first, 20 of 20) - [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022) - [Root Mean Square Layer Normalization](https://mlsanity.com/paper/1910.07467/) (2019) - [On Layer Normalization in the Transformer Architecture](https://mlsanity.com/paper/2002.04745/) (2020) - [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021) - [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018) - [Think before you speak: Training Language Models With Pause Tokens](https://mlsanity.com/paper/2310.02226/) (2023) - [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024) - [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023) - [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022) - [Let's Think Dot by Dot: Hidden Computation in Transformer Language Models](https://mlsanity.com/paper/2404.15758/) (2024) - [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021) - [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023) - [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022) - [Don't be lazy: CompleteP enables compute-efficient deep transformers](https://mlsanity.com/paper/2505.01618/) (2025) - [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022) - [Tighter Bounds on the Expressivity of Transformer Encoders](https://mlsanity.com/paper/2301.10743/) (2023) - [A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers](https://mlsanity.com/paper/2503.03961/) (2025) - [Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages](https://mlsanity.com/paper/2310.13897/) (2023) - [Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers](https://mlsanity.com/paper/2404.04393/) (2024) - [Transformers in Uniform TC0](https://mlsanity.com/paper/2409.13629/) (2024) ## Built on by (most cited first, 19 of 19) - [Scaling Latent Reasoning via Looped Language Models](https://mlsanity.com/paper/2510.25741/) (2025) - [TabPFN-2.5: Advancing the State of the Art in Tabular Foundation Models](https://mlsanity.com/paper/2511.08667/) (2025) - [A Formal Comparison Between Chain of Thought and Latent Thought](https://mlsanity.com/paper/2509.25239/) (2025) - [Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization](https://mlsanity.com/paper/2511.07378/) (2025) - [Stability and Generalization in Looped Transformers](https://mlsanity.com/paper/2604.15259/) (2026) - [Why Are Linear RNNs More Parallelizable?](https://mlsanity.com/paper/2603.03612/) (2026) - [On the Reasoning Abilities of Masked Diffusion Language Models](https://mlsanity.com/paper/2510.13117/) (2025) - [Thoughtbubbles: an Unsupervised Method for Parallel Thinking in Latent Space](https://mlsanity.com/paper/2510.00219/) (2025) - [Context-Free Recognition with Transformers](https://mlsanity.com/paper/2601.01754/) (2026) - [Length Generalization Bounds for Transformers](https://mlsanity.com/paper/2603.02238/) (2026) - [Transformers Provably Learn to Internalize Chain-of-Thought](https://mlsanity.com/paper/2605.28600/) (2026) - [Chain-of-Thought and Compressed Looped Transformers: A Memory-Budget Separation](https://mlsanity.com/paper/2605.30757/) (2026) - [Every Bit Counts: A Theoretical Study of Precision-Expressivity Tradeoffs in Quantized Transformers](https://mlsanity.com/paper/2602.02707/) (2026) - [Geometric Capacity of Transformers: A Tropical Geometry Perspective](https://mlsanity.com/paper/2604.14727/) (2026) - [Looped Diffusion Language Models](https://mlsanity.com/paper/2605.26106/) (2026) - [Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't](https://mlsanity.com/paper/2605.30523/) (2026) - [Depth-Sequence Transformer (DST) for Segment-Specific ICA Calcification Mapping on Non-Contrast CT](https://mlsanity.com/paper/2507.08214/) (2025) - [Exponential Sample Complexity Separation between Flat and Hierarchical Agentic Theorem Provers](https://mlsanity.com/paper/2602.10512/) (2026) - [Hidden Reasoning Must Leak, but Need Not Be Readable: Fundamental Opportunities and Limits for Chain-of-Thought Monitoring](https://mlsanity.com/paper/2609.37312/) (2026) ## Abstract (arXiv) Chain of thought is a natural inference-time method for increasing the computational power of transformer-based large language models (LLMs), but comes at the cost of sequential decoding. Are there more efficient alternatives to expand a transformer's expressive power without adding parameters? We consider transformers with padding tokens as a form of parallelizable test-time compute. We show that averaging-hard-attention, masked-pre-norm transformers with polynomial padding recognize precisely the class mathsfFO-uniform mathsfTC0 of extremely parallelizable problems. While the mathsfTC0 upper bound was known, proving a matching lower bound had been elusive. Further, our novel analysis reveals the precise expanded power of padded transformers when coupled with another form of inference-time compute, namely dynamically increasing depth via looping. Our core technical contribution is to show how padding helps bring the notions of complete problems and reductions, which have been a cornerstone of classical complexity theory, to the formal study of transformers. Armed with this new tool, we prove that padded transformers with O(logd n) looping on inputs of length n recognize exactly the class mathsfFO-uniform mathsfTCd of moderately parallelizable problems. Thus, padding and looping together systematically expand transformers' expressive power: with polylogarithmic looping, polynomially padded transformers recognize precisely the class mathsfFO-uniform mathsfNC, the best that could be expected without losing parallelism (unless mathsfNC = mathsfP). Our results thus motivate further exploration of padding and looping as parallelizable alternatives to chain of thought for test-time compute.