6 papers · 1 filter
Discovering Interpretable Algorithms by Decompiling Transformers to RASP
Xinting Huang, Aleksandra Bakalova, Satwik Bhattamishra +2
Recent work has shown that the computations of Transformers can be simulated in the RASP family of programming languages. These findings have enabled improved understanding of the…
Context-Free Recognition with Transformers
Selim Jerad, Anej Svete, Sophie Hao +2
Transformers excel empirically on tasks that process well-formed inputs according to some grammar, such as natural language and code. However, it remains unclear how they can proce…
Exact Expressive Power of Transformers with Padding
William Merrill, Ashish Sabharwal
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 de…
A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
William Merrill, Ashish Sabharwal
Recent theoretical results show transformers cannot express sequential reasoning problems over long inputs, intuitively because their computational depth is bounded. However, prior…
The Illusion of State in State-Space Models
William Merrill, Jackson Petty, Ashish Sabharwal
State-space models (SSMs) have emerged as a potential alternative architecture for building large language models (LLMs) compared to the previously ubiquitous transformer architect…
The Expressive Power of Transformers with Chain of Thought
William Merrill, Ashish Sabharwal
Recent theoretical work has identified surprisingly simple reasoning problems, such as checking if two nodes in a graph are connected or simulating finite-state machines, that are…