On the Expressive Power of Transformers

The Brain's Blueprint: Why Some Puzzles Are Harder Than Others

Imagine you are trying to teach a robot how to read. You might think the robot just needs to look at letters one by one, like a person scanning a page. But modern super-smart robots, called Large Language Models (LLMs), don't work that way. Instead of reading left-to-right, they use a special trick called a "Transformer." Think of a Transformer like a giant team of detectives working in a room. When they see a sentence, every detective can instantly shout out to every other detective to say, "Hey, I'm looking at this word, and it connects to that word over there!" This allows them to understand context and relationships in a flash, rather than just memorizing a list of rules.

But here is the big question that keeps scientists up at night: Just how smart are these detectives really? Can they solve any puzzle, or are there some riddles that will always stump them? To find the answer, researchers don't just run tests; they look at the robot's "brain" through the lens of computer science math. They compare the Transformer to a family of mathematical machines called "circuits." Imagine these circuits as factories with assembly lines. Some factories are very simple, with short lines and few workers (these are called AC0). Others have longer lines and more powerful tools that can count and compare huge numbers (these are TC0). By figuring out which factory the Transformer is most like, scientists can predict exactly what kinds of problems it can solve and where it hits a wall. This matters because if we know the limits of these models, we can stop expecting them to do magic and start building them to do what they are actually good at.

The Paper's Big Discovery: The Transformer's Power Switch

In their paper, "On the Expressive Power of Transformers," researchers Phokion G. Kolaitis and Rik Sengupta act like architects inspecting a new, high-tech building. They aren't just looking at how pretty the building is; they are measuring its load-bearing capacity to see exactly what it can hold. Their main finding is that the Transformer's power isn't fixed; it changes dramatically based on a few "knobs" or settings, specifically how much precision (how many decimal places it can use for math) and whether it is allowed to think out loud (a technique called Chain-of-Thought).

First, let's look at the Transformer without any extra thinking time. The authors explain that if you give the Transformer a simple, "hard" attention setting (where it picks just one word to focus on) or if you limit its math to very low precision (like using only a few bits of information), it is surprisingly weak. In fact, under these conditions, the Transformer is mathematically equivalent to the simplest type of circuit factory, AC0. This means it can handle basic logic, like checking if a sentence has an even number of words, but it struggles with tasks that require counting or comparing large numbers. It's like a detective who can spot a red hat but can't count how many red hats are in the room.

However, the story gets much more interesting when you turn up the precision. If the Transformer is allowed to use more precise math (specifically, a number of bits that grows with the length of the text, like $\Theta(\log n)$), it levels up. It becomes as powerful as the TC0 circuit factory. This is a significant jump! Now, the Transformer can handle "majority" questions and more complex counting tasks. It's like giving the detective a calculator; suddenly, they can solve puzzles that were impossible before. But even with this upgrade, the paper suggests there is still a ceiling. Without extra help, these models are likely stuck in the TC0 realm and cannot easily solve problems that require deep, step-by-step logical reasoning found in more complex computer classes like PTIME (polynomial time).

The real game-changer, according to the paper, is Chain-of-Thought (CoT). Imagine the Transformer is no longer just a detective looking at a crime scene; now, it's allowed to write a diary of its thoughts before giving the final answer. It can generate intermediate "tokens" (little notes) that it feeds back into itself to help solve the problem. The authors show that this simple change breaks the previous limits.

• If the Transformer is allowed to write a short diary (proportional to the length of the text, or $O(n)$), it can solve problems that take quadratic time (like $n^2$).
• If it can write a very long diary (proportional to a polynomial of the text length, or $poly(n)$), it becomes powerful enough to simulate any standard computer algorithm, reaching the PTIME class.
• And if it has unlimited thinking space and precision, it can simulate a Turing Machine, which is the theoretical definition of a universal computer capable of solving any computable problem.

The paper is very clear about what this means: The Transformer isn't inherently "all-powerful" or "useless." Its ability to solve hard problems depends entirely on how much "scratch paper" (Chain-of-Thought) and how much "math precision" you give it. Without these resources, it is limited to simple, shallow logic. With them, it can climb the ladder of complexity all the way to simulating a full computer.

The authors also point out some specific limitations. They argue that the "hard" attention models (where the robot picks only one word) are strictly weaker than the "soft" attention models (where it weighs many words) and cannot even reach the full power of the simplest circuit class in some cases. Furthermore, they emphasize that while the Transformer can theoretically simulate a Turing Machine with enough Chain-of-Thought, this is a theoretical limit. In the real world, we don't have infinite memory or infinite time to generate infinite intermediate thoughts, so real-world models will always have a practical ceiling lower than the theoretical maximum.

In short, Kolaitis and Sengupta have mapped out the "power grid" of Transformers. They show us that these models are not magic black boxes; they are resource-bounded machines. If you want them to solve a hard puzzle, you can't just ask them to "try harder"; you have to give them the right tools: more precision, more layers, and most importantly, the ability to think step-by-step. The paper concludes that understanding these limits is crucial. It helps us stop expecting these models to do the impossible and start designing them to be the best possible versions of what they are: incredibly powerful, but ultimately bounded, pattern recognizers.