# Efficiently Representing Algorithms With Chain-of-Thought Transformers

arXiv: https://arxiv.org/abs/2606.19697 · HTML: https://mlsanity.com/paper/2606.19697/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning.
- Builds on 5 of its 35 references that are in the map.
- First posted on arXiv 18 Jun 2026.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

## Builds on (most cited first, 5 of 5)

- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [In-context Learning and Induction Heads](https://mlsanity.com/paper/2209.11895/) (2022)
- [Olmo 3](https://mlsanity.com/paper/2512.13961/) (2025)
- [Why Are Linear RNNs More Parallelizable?](https://mlsanity.com/paper/2603.03612/) (2026)

## Built on by (most cited first, 1 of 1)

- [Latest Exact Match Attention](https://mlsanity.com/paper/2609.25802/) (2026)

## Abstract (arXiv)

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 complexity-theoretic analysis, 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 bigO(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 bigO(n log n) steps or run Dijkstra's algorithm in bigO(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.