Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Exact Expressive Power of Transformers with Padding
Authors: Will Merrill, Ashish Sabharwal
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Exact Expressive Power of Transformers with Padding. 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 FO-uniform TCd of moderately parallelizable problems. |
| Researcher Affiliation | Industry | William Merrill Allen Institute for AI EMAIL. Ashish Sabharwal Allen Institute for AI EMAIL. |
| Pseudocode | No | The paper describes theoretical constructs, definitions, and proofs related to transformer expressivity and circuit complexity but does not include any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper presents theoretical results and mathematical proofs concerning the expressive power of transformers and does not mention the release of any source code for the described methodologies. |
| Open Datasets | No | This paper is theoretical, focusing on the expressive power of transformers and circuit complexity, and does not involve experimental evaluation using datasets. |
| Dataset Splits | No | As this paper is purely theoretical and does not involve empirical experiments with datasets, there is no mention of dataset splits. |
| Hardware Specification | No | This theoretical paper does not conduct experiments, and therefore, no hardware specifications are provided. |
| Software Dependencies | No | This theoretical paper focuses on mathematical proofs and does not involve empirical experiments or software implementation details, thus no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is a theoretical work providing proofs and analyses of transformer expressivity, and as such, it does not include details on experimental setup or hyperparameters. |