arxiv_ml 92% Match Theoretical Research Paper Theoretical Computer Scientists,ML Theorists,Researchers in Formal Methods 2 weeks ago

Transformers are Inherently Succinct

large-language-models › model-architecture

📄 Abstract

Abstract: We propose succinctness as a measure of the expressive power of a transformer in describing a concept. To this end, we prove that transformers are highly expressive in that they can represent formal languages substantially more succinctly than standard representations of formal languages like finite automata and Linear Temporal Logic (LTL) formulas. As a by-product of this expressivity, we show that verifying properties of transformers is provably intractable (i.e. EXPSPACE-complete).

Authors (3)

Pascal Bergsträßer

Ryan Cotterell

Anthony W. Lin

Submitted

October 22, 2025

arXiv Category

cs.FL

arXiv PDF

Key Contributions

This paper introduces 'succinctness' as a measure of a transformer's expressive power and proves that transformers can represent formal languages significantly more succinctly than standard representations like finite automata or LTL formulas. As a consequence, it shows that verifying properties of transformers is provably intractable (EXPSPACE-complete).

Business Value

Provides a foundational understanding of the theoretical capabilities and limitations of transformer models, which can inform the design of more efficient architectures and guide expectations about their performance in complex reasoning tasks.

Paper Metadata

Innovation Type

Theoretical

Deployment Feasibility

This is a theoretical result and does not directly involve deployment. It impacts the understanding of deployed models.

Limitations Addressed

Lack of a formal measure for the expressive power of transformer models,Understanding the theoretical limits of what transformers can represent

Performance Gains

Demonstrated superior succinctness of transformers for representing formal languages

Technical Tags

transformerssuccinctnessexpressive powerformal languagesfinite automataLinear Temporal Logic (LTL)computational complexityEXPSPACE-completerepresentational capacity

Research Topics

Theoretical Computer ScienceFormal LanguagesTransformer ArchitecturesComputational ComplexityModel Expressivity

Methods & Architectures

Theoretical AnalysisProof TechniquesFormal Language Theory Transformer

Applications & Tasks

Theoretical Computer Science Formal Verification Automata Theory Measuring expressive power of modelsUnderstanding representational limitsComplexity of verifying transformer properties Representing formal languagesAnalyzing model expressivityDetermining computational complexity of verification

Related Fields

Computer Science TheoryMachine Learning TheoryFormal LanguagesAutomata TheoryTransformer Networks

Keywords

transformerssuccinctnessexpressive powerformal languagesfinite automataLTLcomputational complexityEXPSPACEtheory of computationmodel capacityverification

Academic Context

#Theoretical Computer Science#Formal Languages#Transformer Architectures#Computational Complexity#Model Expressivity

Commercial Potential

Target Industries

TechnologyAcademia

Use Case Examples

Understanding the theoretical limits of LLMsGuiding the development of more efficient sequence models

Competitive Edge

Establishes a theoretical framework for comparing the representational power of transformers against classical computational models.

Resource Requirements

Compute Needs

N/A (Theoretical paper)

Data Requirements

N/A (Theoretical paper)

Deployment Constraints

N/A (Theoretical paper)

Scalability

N/A (Theoretical paper)

Production Readiness

Maturity Level

Theoretical Foundation

View Full Paper Back to Papers