A new theoretical result in machine learning shows that chain-of-thought (CoT) transformers can efficiently simulate algorithms expressed in the Word RAM model, addressing a gap between complexity theory and practical algorithm design. The research, published on arXiv by Li, Yanhong, Svete, Anej, Sabharwal, Ashish, and Merrill, William, answers a key question: can reasoning models like those used in large language models perform arbitrary computation as efficiently as standard algorithms?
The Word RAM Model vs. Turing Machine
The increasing popularity of reasoning models—language models that output a series of reasoning or thought tokens before producing an answer—is partly justified by theoretical results showing that CoT transformers can simulate Turing machines, and thus perform arbitrary computation. However, the Turing machine is not convenient, intuitive, or efficient for discussing algorithms. Algorithms are typically designed and analyzed at a higher level of abstraction, captured by the Word RAM model with random-access memory and unit-cost operations on O(log n)-bit words. Word RAM algorithms can be substantially more efficient than their Turing machine counterparts, raising the question: Can CoT transformers efficiently simulate Word RAM algorithms?
Key Findings
The paper answers affirmatively, up to poly-logarithmic overhead. Specifically, they prove that CoT transformers can sort n items in O(n log n) steps or run Dijkstra's algorithm in O(E + V log V) steps—the same asymptotic complexity as optimal Word RAM implementations. This is achieved in three settings:
| Setting | Width | Precision | Overhead over Word RAM |
|---|---|---|---|
| Finite-precision transformers with rightmost unique hard attention | Poly-logarithmic | Finite | Poly-logarithmic in n |
| Continuous CoT (reasoning as vectors) | Finite | Log-precision | Poly-logarithmic in n |
| Hybrid architecture (transformer layers on recurrent linear RNN) | Finite | Log-precision | Poly-logarithmic in n |
The overhead reduces to log-square when the Word RAM has a "flat" instruction set, and only logarithmic for multiplication-free flat instructions. This starkly contrasts with known CoT simulations of Turing machines, which require quadratic overhead over Word RAM.
Three Practical Settings
The authors first establish the result for finite-precision transformers with poly-logarithmic width and rightmost unique hard attention. They then strengthen the result to two more practical settings with finite width and log-precision: continuous CoT, where reasoning takes the form of vectors rather than tokens, and a hybrid architecture in which transformer layers sit atop a recurrent (linear RNN) layer. In all three cases, they find that CoT can efficiently simulate any Word RAM algorithm with only a poly-logarithmic overhead in n.
Implications for Reasoning Models
"The increasing popularity of reasoning models—language models that output a series of reasoning or thought tokens before producing an answer—is justified, in part, by theoretical results showing that chain-of-thought (CoT) transformers can simulate Turing machines, and thus perform arbitrary computation."
The paper's findings suggest that CoT transformers are not only theoretically powerful but also practically efficient for executing standard algorithms, potentially improving the reasoning capabilities of large language models while maintaining computational efficiency. By proving that CoT transformers can match the efficiency of Word RAM algorithms—the de facto model for algorithm design—this work bridges a critical gap between AI reasoning and classical computer science.