Researchers have proven that chain-of-thought transformers can efficiently simulate the kind of algorithms computer scientists actually use — not just the theoretical minimum.
The paper tackles a gap in prior theoretical work. Earlier results showed that chain-of-thought (CoT) models can simulate Turing machines, which sounds impressive but sets a low bar — Turing machines are deliberately stripped-down abstractions. Real algorithms, like sorting or shortest-path searches, are designed for the Word RAM model, which has random-access memory and cheap operations on multi-bit words. Word RAM lets you sort n items in O(n log n) steps; a Turing machine doing the same work is far slower. The new result shows CoT transformers can match Word RAM performance with only a poly-logarithmic overhead — and that overhead shrinks further for simpler instruction sets, down to logarithmic for multiplication-free flat instructions.
The practical implication is that the theoretical ceiling for reasoning models is higher than the Turing-machine framing suggested. If a CoT model can simulate Dijkstra's algorithm or merge sort at near-optimal step counts, that reframes how researchers should think about what reasoning tokens are actually buying — not just expressibility, but efficiency. It also gives hardware and architecture researchers a more useful benchmark than "can it compute anything at all."
The result holds across three architectural settings, including a hybrid transformer-RNN design, which suggests it is not an artifact of one narrow model class — though the distance between a theoretical simulation and a model that reliably executes an algorithm in practice remains, as ever, considerable.