Internalizing Chain-of-thought into Looped Transformers

Kehang Zhou; Pinyan Lu

cs.CCOct 19, 2026

Internalizing Chain-of-thought into Looped Transformers

Authors: Kehang Zhou, Pinyan Lu

Organizations: Institute for Theoretical Computer Science Shanghai University of Finance and Economics

Abstract

Chain-of-thought (CoT) enables constant-bit-size transformers to perform general-purpose computation through generated tokens (Li and Wang, 2025a), whereas looped transformers carry out the same computation by recurrence in hidden states (latent thought). We construct a family of constant-bit-size looped transformers that interpolates between CoT and latent thought. For a prescribed loop count $L=L(n)$ and a fixed integer $k\ge1$ satisfying $s(n)^{1/k}=Ω(L)$ , our transformer simulates a time- $t(n)$ , space- $s(n)$ Turing machine using a context window of $O(s(n)/L)$ and $O(t(n)s(n)^{1/k}/L)$ generated tokens, reducing both resources by a factor of $L$ relative to the corresponding unlooped queue-machine simulation. The construction also holds with softmax attention at constant bit-size, under the finite-precision kernel specified in this paper.

Figures & tables

Panel of Figure 1 — Figure 1: One pass at position $i$ . At iteration $l$ , head $r$ retrieves queue $r$ ’s front from $V(i-w_{r}+1,l)$ , and the feed-forward network advances the machine by one step. The final write is emitted as the token at position $i+1$ .

Quantity	$L=1$ (endpoint)	admissible $L=O(s(n)^{1/k})$
Generated tokens	$O(t(n)s(n)^{1/k})$	$O\!\big(t(n)s(n)^{1/k}/L\big)$ , exactly $\lceil\tau(n)/L\rceil$
Visible positions (window)	$O(s(n))$	$O\!\big(s(n)/L\big)$
Loop executions (serial block work)	$O(t(n)s(n)^{1/k})$	$O(t(n)s(n)^{1/k})$ , unchanged
Total cached KV state	$\Theta(s(n))$	$\Theta(Lw)=\Theta(s(n))$ , unchanged
Learned model size	$O(1)$ , machine-dependent	$O(1)$ , machine-dependent

Table 1: The construction at the endpoint

L=1

(which recovers the bounds of Li and Wang, 2025b ) and at a general admissible loop count. The simulated Turing machine is the same, while the queue lengths are re-instantiated for each

L

; only the first two rows shrink with

L

Pass $i$	Window	Steps executed	Reads ( $l=0,1,2$ )	Residual advances from	Emits
2	$\{0,1,2\}$	6, 7, 8	$\sigma_{0},\sigma_{1},\sigma_{2}$ (at pos. 0)	6, 7, 8	$(q_{9},\sigma_{9})$
3	$\{1,2,3\}$	9, 10, 11	$\sigma_{3},\sigma_{4},\sigma_{5}$ (at pos. 1)	9, 10, 11	$(q_{12},\sigma_{12})$
4	$\{2,3,4\}$	12, 13, 14	$\sigma_{6},\sigma_{7},\sigma_{8}$ (at pos. 2)	12, 13, 14	$(q_{15},\sigma_{15})$

Table 2: One queue with

L=3

\ell=7

, and

w=3

. At pass

i

and iteration

l

, the head reads position

i-2

in iteration

l

, which is log index

3(i-2)+l=3i+l-7+1

. The pass advances the machine by three steps and emits every third log state.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Source	Precision	Dim.	Depth	Window	CoT per TM-step
Pérez et al. 2021	$O(\log t)$	$O(1)$	$O(1)$	$n+t$	$1$
Bhattamishra et al. 2020	unbounded	$O(1)$	$1$	$n+t$	$1$
Merrill & Sabharwal 2024	$O(\log t)$	$O(1)$	$O(1)$	$n+t$	$1$
Li et al. 2024	$O(1)$	$O(\log t)^{\ddagger}$	$2$	$O(t\log t)$	$O(\log t)$ amort.
Qiu et al. 2025	$O(\log t)$	$O(1)$	$O(1)$	$O(t\log t)$	$O(\log t)$ amort.
Li & Wang 2025a	$O(1)$	$O(1)$	$1$	$s$	$s$

Appendix

Table 3: Comparing transformers simulating

(t,s)

-bounded Turing machines. Depth is the number of sequential decoder layers as reported by each source; for this work it is the loop count

L

—one shared decoder block executed

L

times per generated token. This work prescribes

L

and chooses

k

subject to

s(n)^{1/k}=\Omega(L)

; Li & Wang 2025b is the endpoint

L{=}1

Recurrent Transformers

Recurrent Transformers reuse layers or state across steps to extend context, reasoning depth, and sequence modeling with less parameter growth.

See all 179 papers

Chain-of-Thought and Compressed Looped Transformers: A Memory-Budget Separation
May 29, 2026Haozhou ZhangCoT Reasoning Persistent Memory for Language Models
Department of Mathematics and Statistics University of Idaho
Efficiently Representing Algorithms With Chain-of-Thought Transformers
Jun 18, 2026Yanhong Li, Anej Svete, Ashish Sabharwal +1Transformer CoT Reasoning
Allen Institute for AI · ETH Zürich
Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
Apr 28, 2026Oliver Kraus, Yash Sarrof, Yuekun Yao +2Transformer Expressivity CoT Reasoning
1Saarland University · 2Ohio State University

May 29, 2026J/K move · Enter open · S save

Chain-of-Thought and Compressed Looped Transformers: A Memory-Budget Separation

Haozhou Zhang

Department of Mathematics and Statistics University of Idaho

CoT Reasoning Persistent Memory for Language Models Recurrent Transformers

Open paper AskPDF arXiv

Chain-of-thought prompting and looped Transformers both give a fixed model more test-time computation, but they differ in what they remember. Chain-of-thought stores intermediate state in generated tokens that remain in the context, whereas a looped Transformer carries state through recurrent hidden activations. We argue that this persistent mutable memory is a central resource for test-time reasoning. We compare three memory regimes, the compressed latent loop, the full sequence-state loop, and the chain-of-thought scratchpad. Our main result shows that a compressed loop is limited by the size of its recurrent state. Running the loop longer adds computation but does not by itself create a growing scratchpad, so a loop with a small recurrent state remains a small-space reasoner even when run for many steps. Under a standard complexity assumption, such loops cannot decide problems that are P-complete under logspace reductions, whereas polynomial-length chain-of-thought can. The separation is specific to compressed loops, as full sequence-state loops carry state at every input position and live in a memory-rich regime closer to explicit scratchpads. Controlled pointer-chasing and associative-recall sweeps illustrate this memory-budget view, with performance sensitive to whether the persistent-state budget matches the task's working-memory demand.

Abstract

Recurrent Transformers

Explore similar work

Chain-of-Thought and Compressed Looped Transformers: A Memory-Budget Separation

Efficiently Representing Algorithms With Chain-of-Thought Transformers

Barriers to Universal Reasoning With Transformers (And How to Overcome Them)