Tighter Bounds on the Expressivity of Transformer Encoders

2023/01/25 by David Chiang, Peter Cholak, Chiang, David +3 · 1 voice · 16 citations
Computer Science · Engineering · #Algorithm #Computer science #Electrical engineering #Encoder #Engineering #Ferroelectric and Negative Capacitance Devices #Machine Learning and Algorithms #Neural Networks and Applications #Theoretical computer science #Transformer #Voltage #cs.FL #cs.LG #cs.LO

paper · pdf · doi:10.48550/arxiv.2301.10743

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2023/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

Characterizing neural networks in terms of better-understood formal systems has the potential to yield new insights into the power and limitations of these networks. Doing so for transformers remains an active area of research. Bhattamishra and others have shown that transformer encoders are at least as expressive as a certain kind of counter machine, while Merrill and Sabharwal have shown that fixed-precision transformer encoders recognize only languages in uniform TC⁰. We connect and strengthen these results by identifying a variant of first-order logic with counting quantifiers that is simultaneously an upper bound for fixed-precision transformer encoders and a lower bound for transformer encoders. This brings us much closer than before to an exact characterization of the languages that transformer encoders recognize.

Cited by

• Indexing: the Beginning and the End
• Rectifying LLM Thought from Lens of Optimization
• Analyzing the Power of Chain of Thought through Memorization Capabilities
• The Transformer Cookbook
• Transformers through the lens of support-preserving maps between measures
• Efficient Turing Machine Simulation with Transformers
• Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers
• Topos Theory for Generative AI and LLMs
• Syntax Repair as Language Intersection
• Characterizing the Expressivity of Fixed-Precision Transformer Language Models
• Deciphering Trajectory-Aided LLM Reasoning: An Optimization Perspective
• Exact Expressive Power of Transformers with Padding
• Length Generalization Bounds for Transformers
• Characterizing the Expressivity of Local Attention in Transformers
• Protoreasoning in Tiny Transformers
• Attention-based representations for multi-task computation

Discussions

• Tighter bounds on the expressivity of transformer encoders [hn, 76 points, 13 comments]

Related

• How Powerful are Decoder-Only Transformer Neural Models?
• Transformers are Inherently Succinct
• A Logic for Expressing Log-Precision Transformers
• Transformers are Expressive, But Are They Expressive Enough for Regression?
• Characterizing the Expressivity of Fixed-Precision Transformer Language Models