Efficiently Representing Algorithms with Chain-of-Thought Transformers

While it is well-established that chain-of-thought (CoT) transformers are Turing complete, existing theoretical constructions rely on simulating Turing machines (TMs). TMs are inefficient for modeling random-access memory (RAM) operations, leading to a quadratic overhead when simulating standard algorithms. This paper investigates whether CoT transformers can directly simulate the Word RAM model—the standard abstraction for textbook algorithms—more efficiently.

The authors demonstrate that CoT transformers can simulate Word RAM programs by directly mapping RAM operations to transformer reasoning steps. They explore three distinct architectures to achieve this:

1. Polylogarithmic-width transformers: Using rightmost unique hard attention to manage memory reads and writes.
2. Fixed-width transformers with continuous CoT: Replacing discrete tokens with hidden vector representations to invoke a TM oracle for each instruction.
3. Hybrid transformer-RNN models: Augmenting standard transformers with a linear RNN layer to handle the memory state and instruction execution.

The study proves that all three architectures can simulate any Word RAM algorithm with only poly-logarithmic overhead in the input size $n$. Specifically, for "flat" instruction sets (common in basic programming), the overhead is reduced to logarithmic or log-square factors. This is a substantial improvement over the quadratic overhead required by TM-based simulations. The authors show that these constructions are nearly optimal, matching information-theoretic lower bounds for discrete CoT.

This work bridges the gap between theoretical transformer expressivity and practical algorithm implementation. By showing that transformers can execute textbook algorithms (like sorting or Dijkstra’s) with minimal overhead, the paper provides a formal basis for why reasoning models are effective at complex, multi-step tasks. It suggests that the "reasoning" observed in modern LLMs is not just a heuristic, but a computationally efficient way to perform algorithmic logic.