🤖 machine learning

Efficiently Representing Algorithms With Chain-of-Thought Transformers

This paper demonstrates that Chain-of-Thought transformers can efficiently simulate Word RAM algorithms with only poly-logarithmic overhead, significantly outperforming the quadratic overhead required for Turing machine simulations.

Original authors: Yanhong Li, Anej Svete, Ashish Sabharwal, William Merrill

Published 2026-06-19

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Yanhong Li, Anej Svete, Ashish Sabharwal, William Merrill

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Core Problem: The "Tape" vs. The "Desk"

Imagine you are trying to solve a complex math problem.

The Old Way (Turing Machines):
Think of a Turing Machine like a student who has only a single, infinitely long strip of paper (a tape). To look at a number they wrote down three pages ago, they have to physically walk back along the paper, step by step, until they find it. If they want to sort a list of 1,000 names, they have to walk back and forth across that tape thousands of times. It works, but it is incredibly slow and tedious. This is how most previous computer science theories proved that AI could "think."

The Real Way (Word RAM):
Now, imagine a student with a large desk and a filing cabinet. This is the Word RAM model. They can grab any file from the cabinet instantly (random access). They can do math on whole numbers at once, not bit-by-bit. This is how real algorithms (like sorting lists or finding the shortest path on a map) are actually written in textbooks. It is much faster.

The Question:
We know that AI models with "Chain-of-Thought" (CoT)—where the AI writes out its reasoning steps before giving an answer—can simulate the slow "Tape" student. But can they simulate the fast "Desk" student efficiently? Or does the AI get bogged down in the slowness of the tape method, making it useless for real-world tasks?

The Paper’s Answer: Yes, But It Needs the Right Tools

The authors prove that yes, Chain-of-Thought Transformers can simulate these fast, real-world algorithms efficiently. They don’t get stuck in the slow "tape" bottleneck. However, to do this, the AI needs to use specific "tricks" or architectural tweaks.

They show this works in three different scenarios, which we can think of as three different types of "thinking pads" the AI uses:

1. The "Wide Notebook" (Polylog-Width Transformers)

The Analogy: Imagine the AI has a notebook that gets wider as the problem gets harder. If the problem is huge, the notebook is very wide.
How it works: The AI writes down the entire state of its memory in binary code (0s and 1s) across the width of the page. Because the page is wide enough, it can look up information quickly.
The Cost: It’s efficient, but the notebook size changes depending on the problem. It’s not a "one-size-fits-all" tool.

2. The "Ghostly Scratchpad" (Continuous CoT)

The Analogy: Imagine the AI has a standard-sized notebook, but it can also write in "invisible ink" that only it can see. This invisible ink isn't just text; it’s a mathematical vector (a direction and magnitude).
How it works: Instead of writing out every single bit of a number, the AI writes a compact "summary" (a hash) in this invisible ink. It can pass this summary from one step to the next without rewriting the whole number. When it needs to do detailed math, it "decodes" the invisible ink into bits, does the work, and then re-encodes it.
The Benefit: This allows the AI to keep its "desk" organized and fast, even with a fixed-size notebook.

3. The "Memory Helper" (Hybrid Transformer-RNN)

The Analogy: Imagine the AI has a standard notebook, but it also has a very short-term memory assistant (a Recurrent Neural Network, or RNN) standing next to it.
How it works: The AI writes the main steps in the notebook, but the assistant holds the current "state" of the calculation in its head. The assistant can quickly update the numbers (like dividing by 2 or adding a bit) and hand the result back to the AI.
The Benefit: This combines the best of both worlds: the Transformer’s ability to look back at the whole history, and the RNN’s ability to carry information forward smoothly.

Why This Matters (The "Overhead")

In computer science, "overhead" is the extra time or effort needed to do a task.

The Old Method: If you forced a Chain-of-Thought AI to use the old "Tape" method to sort a list, the overhead was quadratic. If sorting 10 items took 100 steps, sorting 100 items might take 10,000 steps. It grows too fast.
The New Method: This paper shows that with the right setup (the three methods above), the overhead is only poly-logarithmic. This is a fancy way of saying it grows very slowly. If sorting 10 items takes 100 steps, sorting 100 items might only take a few hundred steps. It stays close to the speed of the original algorithm.

The "Bit Extraction" Challenge

A major hurdle the authors solved was bit extraction.

The Problem: To do math, the AI needs to look at individual bits (0s and 1s). But in the efficient models (like the Ghostly Scratchpad), the numbers are stored as compact summaries, not as lists of bits.
The Solution: The authors proved that the AI can "peel off" bits one by one from these summaries. It’s like having a sealed envelope (the summary) and being able to pull out one letter (bit) at a time, read it, and then update the envelope for the next letter, without opening the whole thing at once.

Summary

This paper is a theoretical proof that AI reasoning (Chain-of-Thought) is not just a gimmick; it can be as efficient as the algorithms humans write.

Before: We knew AI could simulate computers, but only in a slow, clunky way (like the tape student).
Now: We know AI can simulate computers in a fast, efficient way (like the desk student), provided we give it the right tools (wide notebooks, invisible ink, or memory assistants).

This bridges the gap between theory (what computers can do) and practice (how we actually write code), showing that the "thinking" process of modern AI models is fundamentally capable of handling complex, real-world logic efficiently.

Technical Summary: Efficiently Representing Algorithms with Chain-of-Thought Transformers

Problem Statement
While it is established that Chain-of-Thought (CoT) transformers are Turing complete—capable of simulating any Turing machine (TM)—this theoretical universality does not guarantee efficiency for practical algorithmic tasks. Standard complexity analysis for algorithms relies on the Word Random Access Machine (Word RAM) model, which allows random access to memory and unit-cost operations on $O(\log n)$ -bit words. In contrast, TMs lack random access, requiring linear time to traverse tape positions. Consequently, simulating a Word RAM algorithm on a TM incurs a quadratic overhead ( $O(t^2)$ for $t$ steps). Existing CoT constructions simulate TMs directly, inheriting this quadratic inefficiency. The central question addressed in this paper is whether CoT transformers can efficiently simulate Word RAM algorithms directly, matching their textbook complexity bounds (e.g., $O(n \log n)$ for sorting) up to only poly-logarithmic overhead, rather than the quadratic overhead of TM-based simulations.

Methodology
The authors propose direct simulations of Word RAM programs by CoT transformers, bypassing the intermediate TM simulation. They analyze three distinct transformer settings to achieve this efficiency:

Polylogarithmic-Width Transformers: This setting uses finite-precision transformers with width $O(\log^2 n)$ and rightmost-unique hard attention (UHAT). Values are represented as binary vectors in the residual stream. The simulation logs memory writes to the CoT transcript as address-value pairs. Memory reads are performed using indexed attention mechanisms that retrieve the most recent write to a specific address.
Continuous CoT (CCoT): This setting uses fixed-width, log-precision transformers where reasoning steps emit continuous "soft tokens" (real-valued vectors) alongside discrete tokens. This allows the model to maintain persistent state (such as Layer-Norm hashes of values) across decoding steps without expanding the discrete transcript width.
Hybrid Transformer-RNN Models: This setting combines fixed-width transformers with a linear Recurrent Neural Network (RNN) layer. The RNN component handles the persistence of value representations (Layer-Norm hashes) across time steps, serving as a practical alternative to continuous CoT.

A key technical component across the fixed-width settings (2 and 3) is the use of Layer-Norm Hashes ( $\phi(v)$ ) to represent values. This representation allows for exact equality checks via inner products and supports affine updates, enabling the serialization and deserialization of values into bit streams for arithmetic operations. The authors also introduce a "restricted" Word RAM normal form, ensuring that all values $v$ at step $s$ satisfy $v \le s$ , which simplifies bit extraction and division operations.

Key Contributions
The paper provides theoretical proofs that CoT transformers can simulate Word RAM algorithms with poly-logarithmic overhead in three specific architectures:

Polylog-Width Simulation (Theorem 1): A finite-precision transformer with $O(\log^2 n)$ width and rightmost UHAT can simulate a flat Word RAM program. For a program running $t$ steps with word size $w = \Theta(\log(n+t))$ , the simulation requires $O(t \cdot w^2) = O(t \log^2(n+t))$ CoT tokens. If the instruction set excludes multiplication, division, and modulo, the overhead reduces to $O(t \cdot w) = O(t \log(n+t))$ .
Continuous CoT Simulation (Theorem 3): A fixed-width, log-precision transformer with continuous CoT can simulate any Word RAM program in $O(t \cdot \kappa(w))$ decoding steps, where $\kappa(w)$ is the TM cost of executing one Word RAM instruction. For flat instruction sets, this yields $O(t \log(n+t))$ for simple arithmetic and $O(t \log^2(n+t))$ for full arithmetic.
Hybrid Model Simulation (Theorem 4): A fixed-width hybrid model (Transformer + linear RNN) achieves the same $O(t \cdot \kappa(w))$ complexity as the continuous CoT setting, demonstrating that recurrence can substitute for continuous soft tokens in maintaining state.

Results

Efficiency Gain: The proposed simulations reduce the overhead from quadratic ( $O(t^2)$ ) in TM-based CoT simulations to poly-logarithmic ( $O(t \log^2 n)$ or $O(t \log n)$ ).
Tightness: For discrete CoT with simple arithmetic, the $O(t \log n)$ overhead matches the information-theoretic lower bound of $\Omega(t \log n)$ , as representing a $w$ -bit word requires $\Omega(w)$ tokens.
Instruction Set Dependence: The overhead depends on the complexity of the Word RAM instructions. "Flat" instruction sets (no nested expressions) allow for efficient simulation. Multiplication, division, and modulo operations require $O(w)$ micro-steps, leading to the $O(w^2)$ per-instruction overhead in the polylog-width setting, whereas simple arithmetic (addition, bitwise ops) requires only $O(w)$ .

Significance
The paper argues that these results justify the empirical practice of training reasoning models to solve complex tasks by showing that CoT transformers can execute textbook algorithms with near-native efficiency. It closes the gap between the theoretical Turing completeness of transformers and the practical efficiency required for algorithmic reasoning. By demonstrating that minimal architectural extensions (continuous CoT or RNN layers) enable fixed-width transformers to simulate Word RAMs efficiently, the paper highlights that the quadratic overhead of previous TM-based simulations was an artifact of the simulation method, not an inherent limitation of CoT transformers. The work establishes that CoT, under certain architectural conditions, allows for the simulation of algorithms with their general textbook runtimes up to a polylogarithmic factor.