Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers

2024/04/05 by Yang, Andy, Chiang, David · 8 citations
#Computation and Language (cs.CL) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2404.04393

Abstract

Deriving formal bounds on the expressivity of transformers, as well as studying transformers that are constructed to implement known algorithms, are both effective methods for better understanding the computational power of transformers. Towards both ends, we introduce the temporal counting logic \textsfK_t[#] alongside the RASP variant \textsfC-RASP. We show they are equivalent to each other, and that together they are the best-known lower bound on the formal expressivity of future-masked soft attention transformers with unbounded input size. We prove this by showing all \textsfK_t[#] formulas can be compiled into these transformers.

Cited by

• Softmax Transformers are Turing-Complete
• Probability Distributions Computed by Hard-Attention Transformers
• Quantitative Bounds for Length Generalization in Transformers
• The Geometry of Reasoning: Flowing Logics in Representation Space
• Post-Norm can Resharpen Attention
• The Transformer Cookbook
• The Role of Logic and Automata in Understanding Transformers
• A model of errors in transformers

Related

• The Counting Power of Transformers
• When Can Transformers Count to n?
• Counting and Algorithmic Generalization with Transformers
• Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages
• Softmax Transformers are Turing-Complete