Beyond Transformers: Recent Work By CDS PhD Student William Merrill
Imagine you gave ChatGPT a map of roads and cities, and asked, “Is it possible to get from City A to City B?” Would you expect the right answer? Theoretical insights from CDS PhD student William Merrill’s research prove that, in general, the language model cannot give you the right answer to this question, as well as many simple questions.
In recents talks at the NYC AI Collective and the Simons Institute in September, Merrill presented findings from his years-long investigation into the computational capabilities of transformer neural networks — the architecture powering models like ChatGPT and Anthropic’s Claude. His work revealed that these systems, despite their apparent sophistication, cannot perform certain basic computational tasks that even simple computer programs can handle.
“There are surprisingly elementary problems that transformers without chain-of-thought fundamentally cannot solve, no matter how you train them,” Merrill said. “For instance, they cannot reliably determine if there’s a path between two points in a network graph.” (This research was previously discussed on the blog.)
Merrill’s research placed transformers within a hierarchy of computational complexity classes, demonstrating that they operate at a relatively basic level called TC0. This classification proved that transformer models cannot handle tasks requiring sequential processing — where each step must build on previous ones.
This limitation manifests in concrete ways. Beyond graph connectivity problems, transformers struggle with tasks like tracking the state of a board game or video game as the player makes moves, or evaluating certain types of mathematical formulas. In testing, models like ChatGPT frequently gave incorrect answers to these types of problems, even in simple cases.
However, in their paper “The Expressive Power of Transformers with Chain of Thought,” Merrill and Ashish Sabharwal of Ai2 discovered that these computational limitations can be overcome through chain of thought reasoning, where models generate intermediate steps before producing a final answer. With enough chain of thought steps, they show that transformers can solve previously impossible problems like graph connectivity, tracking game states, or evaluating complex formulas. However, this requires a large number of chain of thought steps: with fewer steps, the power of transformers remains close to TC0. (Along with CDS PhD Student Jacob Pfau and CDS Associate Professor of Linguistics and Data Science Sam Bowman, Merrill also considered ‘pause tokens’, a variant of chain-of-thought, which we also covered previously on the blog.)
Another promising direction explores alternative neural architectures called state space models. Merrill shows that minimally altered versions of SSMs can solve more complex problems, namely those in the NC1 class, which is more powerful than TC0.
Merrill’s findings suggest that the field’s heavy focus on transformer architectures may need reconsideration. Transformers have been successful in part because their parallel architecture makes it possible to train them on lots of data. But Merrill’s research suggests this scalability comes with a cost. “There’s a fundamental tension between the parallel processing that makes these models efficient to train and their ability to handle sequential reasoning,” Merrill said. “To create AI systems capable of complex sequential reasoning, we currently need to rely heavily on chain of thought and may eventually need to look beyond pure transformer architectures.”
This tension is particularly evident in chain-of-thought approaches. While adding intermediate reasoning steps gives transformers more computational power, it sacrifices the parallel processing that makes them efficient to train and run. It’s a concrete example of what Merrill calls the parallelism tradeoff: gaining the ability to handle sequential reasoning often means losing the very parallelism that made transformers successful in the first place.
Merrill’s research represents a significant step towards theoretical understanding of both the capabilities and limitations of current AI systems. By precisely characterizing what these models cannot do, his work helps chart a course toward more capable artificial intelligence architectures. The research emerged from a collaboration that began during Merrill’s previous role at the Allen Institute for AI, leading to a series of papers that methodically mapped out the computational powers and limitations of transformer neural networks. This theoretical work provides crucial insights for the next generation of AI architectures.
By Stephen Thomas
