Efficiently Representing Algorithms With Chain-of-Thought Transformers

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. However, the Turing machine, while suitable for a complexity theoretic analysis, isn't convenient, intuitive, or efficient when 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. As a result, Word RAM algorithms can be substantially more efficient than their Turing machine counterparts, raising the question: *Can CoT transformers efficiently simulate Word RAM algorithms?* For instance, can they sort $n$ items in $O(n \log n)$ steps or run Dijkstra's algorithm in $O(E + V \log V)$ steps? We answer affirmatively, up to poly-logarithmic overhead. We first establish this for finite-precision transformers with poly-logarithmic width and rightmost unique hard attention, 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, we find that CoT *can* efficiently simulate any Word RAM algorithm with only a poly-logarithmic overhead in $n$. This overhead reduces to log-square when the Word RAM has a ``flat'' instruction set, and only logarithmic for multiplication-free flat instructions---in stark contrast to known CoT simulations of Turing machines, which require quadratic overhead over Word RAM.