How Intermediate Tokens Bypass the TC0 Complexity Limit in Transformers

A traditional computer processor executes instructions sequentially, building complexity over time by feeding the output of one operation directly into the next. A standard transformer neural network does the exact opposite. It processes entire sequences simultaneously in parallel, trading sequential time for massive spatial computation.[7]

This parallel architecture is the engine behind modern artificial intelligence, allowing models to train efficiently on trillions of words. However, that same structural advantage imposes a strict mathematical ceiling on what the network can compute in a single pass.[2]

Researchers from the Allen Institute for AI and New York University have mapped this limitation using formal circuit complexity. They demonstrated that a transformer generating a single answer immediately after reading a prompt is trapped within a restricted computational class known as TC0.[6]

This means there are inherently serial problems—like tracking states, simulating finite automata, or solving modular arithmetic—that a standard transformer simply cannot solve in one step. No amount of parameter scaling or training data can bypass this hard architectural limit.[5]

Yet, frontier models routinely solve these exact problems. They do so by generating intermediate reasoning steps, a technique known as chain-of-thought prompting.[4]

While originally viewed as a cognitive heuristic that mimics human reasoning, theoretical computer science now reveals a different reality. Generating intermediate tokens is a structural requirement that mathematically multiplies the network's depth, converting parallel spatial computation into the serial temporal computation needed to bypass the TC0 barrier.[1]

The Mathematical Ceiling of Parallelism

To understand why transformers hit a wall, one must look at how they process data. When a prompt enters a transformer, the attention mechanism compares every token against every other token simultaneously.[7]

This highly parallel operation is bounded by the network's fixed number of layers. If a model has 96 layers, the data undergoes exactly 96 sequential transformations before producing an output.[7]

In computational complexity theory, this structure is equivalent to a constant-depth threshold circuit. In 2022, researchers William Merrill and Ashish Sabharwal proved that transformers with saturated attention are upper-bounded by the TC0 complexity class.[6]

TC0 circuits can perform basic arithmetic, sort data, and count items, but they cannot execute sequential logic where step 50 strictly depends on the outcome of step 49. The depth of the computation is fixed, regardless of how long or complex the input sequence becomes.[6]

"We thus speculatively introduce the idea of a fundamental parallelism tradeoff," Merrill and Sabharwal wrote in their 2023 paper for the Association for Computational Linguistics.[2]

"Any model architecture as parallelizable as the transformer will obey limitations similar to it," the researchers concluded, pointing to a potential inherent weakness in the current paradigm of scaling language models.[3]

Why Transformers Fail at Serial Logic

Because of this parallelism tradeoff, standard transformers struggle with tasks that require iterative state tracking. A classic example is the parity problem: determining whether a string of ones and zeros contains an even or odd number of ones.[5]

For a human or a traditional sequential algorithm, parity is trivial. You simply read the string from left to right, flipping a mental switch every time you encounter a one. The final state of the switch gives the answer.[7]

A fixed-depth transformer cannot do this efficiently for long sequences. Because it processes all tokens at once, it lacks the recurrent memory state needed to track the running total across an arbitrary number of steps.[5]

Similarly, evaluating complex mathematical equations or simulating the steps of a finite-state machine falls outside the TC0 boundary. These problems belong to higher complexity classes like NC1 or P, which require computational depth that scales with the size of the input.[1]

If a problem requires 500 sequential steps to solve, a 96-layer transformer cannot compress that logic into 96 forward passes. The network will inevitably hallucinate or guess, lacking the structural capacity to compute the true answer.[7]

The Mechanics of Intermediate Generation

This is where chain-of-thought prompting fundamentally alters the architecture's capabilities. When a model is instructed to "think step by step," it does not just change the text it outputs; it changes the underlying physics of its computation.[4]

Every time a transformer generates a single token, it must execute a complete forward pass through all of its layers. If a model generates 100 intermediate tokens before arriving at a final answer, it has effectively executed 100 consecutive forward passes.[7]

Crucially, each new forward pass can attend to the tokens generated by the previous passes. The output of step one becomes the input for step two, creating a recurrent loop that the base architecture lacks.[7]

By writing intermediate thoughts to the context window, the transformer uses the output sequence as an external scratchpad. This allows the model to store the running state of a serial computation, completely bypassing the constant-depth limitation of its internal layers.[1]

Researchers Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma formalized this in a 2024 study. They proved that chain-of-thought empowers transformers to solve inherently serial problems that are mathematically impossible for the base model to resolve directly.[5]

Scaling Complexity with Token Count

The expansion of expressive power scales directly with the number of intermediate tokens generated. In a 2023 study published on arXiv, researchers quantified exactly how different lengths of chain-of-thought impact a model's theoretical limits.[1]

If a transformer generates a logarithmic number of intermediate steps relative to the input size, its computational power increases only slightly. It remains confined to a relatively weak complexity class known as Log-Space, or L.[1]

However, if the model generates a linear number of intermediate tokens—scaling proportionally with the input length—it crosses a critical threshold. The transformer gains the ability to recognize all regular languages and simulate finite automata, entering the NC1 complexity class.[1]

When the number of intermediate steps scales polynomially, the transformation is even more profound. The researchers demonstrated that polynomial steps allow a transformer to recognize exactly the class of polynomial-time solvable problems, known as P.[1]

This provides the first exact characterization of transformer capabilities in terms of standard complexity classes. It proves that a fixed-depth model can compute anything a traditional polynomial-time algorithm can, provided it is allowed to generate enough intermediate tokens.[1]

The Future of Test-Time Compute

These theoretical proofs explain the empirical success of modern reasoning models. Systems like OpenAI's o1 and DeepSeek's R1 rely heavily on extended inference-time computation, generating thousands of hidden reasoning tokens before responding to a user.[7]

By doing so, they effectively transform a 100-layer neural network into a 10,000-layer neural network on the fly. This dynamic depth allows them to solve intricate coding, mathematics, and logic puzzles that standard models fail on.[7]

This shift represents a transition from scaling training compute to scaling test-time compute. Instead of building deeper networks with thousands of layers, developers can achieve the same computational depth dynamically by forcing the model to generate longer chains of thought.[7]

However, this serial decoding process is computationally expensive. Because each token requires a full forward pass, generating a 2,000-token reasoning chain consumes significantly more energy and time than a standard immediate response.[7]

Ultimately, the mathematical realities of the TC0 limit dictate the future of artificial intelligence architecture. To solve complex, multi-step reasoning problems, models must either sacrifice their parallel efficiency or rely on the recurrent depth provided by intermediate generation.[7]