Efficiently Representing Algorithms With Chain-of-Thought Transformers

• URL: http://arxiv.org/abs/2606.19697v1
• Date: Thu, 18 Jun 2026 01:49:29 GMT
• Title: Efficiently Representing Algorithms With Chain-of-Thought Transformers
• Abstract summary: Chain-of-thought transformers can simulate Turing machines, and thus perform arbitrary computation.<n>We show that CoT emphcan efficiently simulate any Word RAM algorithm with only a poly-logarithmic overhead in $n$.
• Score: 45.60818649759173
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The increasing popularity of \emph{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 \emph{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: \emph{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: \emph{continuous} CoT, where reasoning takes the form of vectors rather than tokens, and a \emph{hybrid} architecture in which transformer layers sit atop a recurrent (linear RNN) layer. In all three cases, we find that CoT \emph{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.

Related papers

• On the Computational Hardness of Transformers [14.73362105392153]
  We show that transformers can be computed more efficiently than $LH$ independent evaluations of attention.<n>In the small embedding regime, computing $LH$ attention heads separately takes $LHN2 + o(1)$ time.<n>In the large embedding regime, one can compute $LH$ attention heads separately using $LHN+ o(1)$ arithmetic operations.
  arXiv  Detail & Related papers  (2026-03-11T21:48:43Z)
• Unifying Graph Measures and Stabilizer Decompositions for the Classical Simulation of Quantum Circuits [0.0]
  We present two new algorithms to simulate an $n$-qubit circuit $C$.<n>The proposed algorithms are simple, only require a linear amount of memory, are trivially parallel, and interact nicely with ZX-diagram simplification routines.
  arXiv  Detail & Related papers  (2026-03-06T15:27:23Z)
• Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations [1.1694898979785655]
  We present optimized quantum circuits for multiplication and division operations.<n>Our ancilla-free GF multiplication circuit has the gate count complexity of $O(mlog3)$.<n>We demonstrate practical advantages for cryptographically relevant values of $m$, including reductions in both CNOT and Toffoli gate counts.
  arXiv  Detail & Related papers  (2025-11-25T18:43:08Z)
• Efficient Turing Machine Simulation with Transformers [6.70318953627082]
  Constant bit-size Transformers are known to be Turing complete.<n>Existing constructions require $(s(n))$ chain-of-thought steps per simulated Turing machine step.<n>We prove that any $(t(n),s(n)$-bounded multi-tape TM can be simulated by a constant bit-size Transformer.
  arXiv  Detail & Related papers  (2025-09-28T01:30:39Z)
• Can Transformers Learn $n$-gram Language Models? [77.35809823602307]
  We study transformers' ability to learn random $n$-gram LMs of two kinds. We find that classic estimation techniques for $n$-gram LMs such as add-$lambda$ smoothing outperform transformers.
  arXiv  Detail & Related papers  (2024-10-03T21:21:02Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  Chain of thought (CoT) is a highly effective method to improve the accuracy of large language models (LLMs) on arithmetics and symbolic reasoning tasks. This work provides a theoretical understanding of the power of CoT for decoder-only transformers through the lens of expressiveness.
  arXiv  Detail & Related papers  (2024-02-20T10:11:03Z)
• How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation [12.853829771559916]
  We study a generalization of attention which captures triple-wise correlations. This generalization is able to solve problems about detecting triple-wise connections that were shown to be impossible for transformers. We show that our construction, algorithms, and lower bounds naturally generalize to higher-order tensors and correlations.
  arXiv  Detail & Related papers  (2023-10-06T07:42:39Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  We find that a low-depth Transformer can represent the computations of any finite-state automaton. We show that a Transformer with $O(log T)$ layers can exactly replicate the computation of an automaton on an input sequence of length $T$. We further investigate the brittleness of these solutions and propose potential mitigations.
  arXiv  Detail & Related papers  (2022-10-19T17:45:48Z)
• Mixability made efficient: Fast online multiclass logistic regression [68.8204255655161]
  We show that mixability can be a powerful tool to obtain algorithms with optimal regret. The resulting methods often suffer from high computational complexity which has reduced their practical applicability.
  arXiv  Detail & Related papers  (2021-10-08T08:22:05Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.