Summary (Overview)

• This paper constructs a family of constant-bit-size looped transformers that interpolates between explicit chain-of-thought (CoT) reasoning and latent thought (internal hidden-state recurrence).
• For a prescribed loop count $L = L(n)$ and fixed integer $k \geq 1$ with $s(n)^{1/k} = \Omega(L)$, the 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 works with hardmax attention and also holds with softmax attention at constant bit-size under a finite-precision kernel specified in the paper.
• The loop count $L$ acts as an "exchange rate" between the external trace (generated tokens) and internal computation (latent iterations), with explicit and latent reasoning being two placements of the same general-purpose computation.
• At $L = 1$, the bounds recover the results of Li and Wang [2025b, Thm 1].

Introduction and Theoretical Foundation

Background

Transformers can perform general-purpose computation through recurrence. Two forms of recurrence exist:

1. Autoregressive generation (CoT): the model appends tokens to its sequence, using them for intermediate computation [Wei et et al., 2022].
2. Looped transformers: a shared block is applied repeatedly to the hidden state, carrying intermediate results in latent representations [Giannou et al., 2023, Yang et al., 2024, Geiping et al., 2025].

Prior Work and Motivation

• Pérez et al. [2021] proved autoregressive transformers are Turing-complete, with precision growing with input.
• Li and Wang [2025a] achieved constant-bit-size Turing completeness with fixed relative offsets and $O(s(n))$ context.
• Li and Wang [2025b] reduced CoT tokens to $O(s(n)^{1/k})$ per simulated machine step by increasing the head–layer product.
• Saunshi et al. [2025] showed loop iterations can simulate CoT steps one-for-one.

Key question: How does moving computation from generated tokens into hidden-state recurrence change the context window and number of generated tokens required for Turing-machine simulation?

Theoretical Foundation

The paper simulates Turing machines through an intermediate synchronous multi-queue machine (Post machine variant). The conversion is cited from Li and Wang [2025b]:

Fact 2.2: For every fixed integer $k \geq 1$, a $t(n)$-time, $s(n)$-space $k'$-tape Turing machine converts to a synchronous $K = 6kk'$-queue machine running in $O(t(n)s(n)^{1/k})$ steps and $O(k's(n))$ total queue space.

Each tape becomes two stacks, each stack $k$ levels of queues. With $B = \lceil s(n)^{1/k} \rceil$, level $g$ uses two content-half queues of length $B^g$ and one buffer of length $2B^g$.

Methodology

Looped Transformer Model

A looped transformer consists of:

• A loop unit $u_\varphi$: a stack of $p \geq 1$ decoder layers with shared weights $\varphi$
• Embedding emb and output head $W_{\text{out}}$, applied outside the loop
• A loop count $L \in \mathbb{N}$

The forward pass computes:

$$h_i^{(0)} = \mathrm{emb}(v_i), \qquad h_i^{(l+1)} = u_\varphi(h_i^{(l)}; C_i^{(l)}) \quad (0 \leq l < L),$$ $$v_{i+1} = \mathrm{argmax}(W_{\text{out}} h_i^{(L)}),$$

Per-Iteration Cache Reading Rule

The cache $C_i^{(l)}$ holds iteration-$l$ key and value entries of retained positions $j < i$. Iteration $l$ of position $i$ attends only to same-iteration entries. A fixed iteration never reads another iteration's cache.

Key Construction Elements

Token layout: At nonterminal position $i$, the token is $(q_{Li}, \sigma_{Li})$ where $\sigma_{Li} = (\sigma_{Li}^{(0)}, \ldots, \sigma_{Li}^{(K-1)}) \in \Sigma^K$ is the tuple appended at log index $Li$.

Embedding layout:

$$h_i^{(0)} = (1, e_{q_{Li}}, \mathrm{onehot}(\sigma_{Li}^{(0)}), \ldots, \mathrm{onehot}(\sigma_{Li}^{(K-1)}), 0^{|\Sigma|K})$$

Positional encoding: With $d_k = K$,

$$\operatorname{pos}(i-j) = \Delta \sum_{r: i-j = w_r - 1} e_r$$

so that $\operatorname{score}_r(i,j) = \Delta[i-j = w_r-1]$, selecting the front of queue $r$ at a fixed relative offset.

Queue lengths: $\ell_r \equiv 1 \pmod{L}$, with $\ell_r = L(w_r - 1) + 1$, ensuring $\ell_r - 1 = L(w_r - 1)$.

Loop Invariant (Lemma 4.1)

For every position $i$ and iteration $l$, the value entry $V(i,l)$ encodes the $K$-tuple at log index $Li + l$. The proof shows that head $r$ attends to position $i - w_r + 1$, whose iteration-$l$ entry is:

$$V(i - w_r + 1, l)^{(r)} = \sigma_{Li+l-\ell_r+1}^{(r)}$$

which is exactly the front of queue $r$ for step $Li + l$.

Empirical Validation / Results

Main Theorem (Theorem 4.3)

Any $(t(n), s(n))$ time-space bounded $k'$-tape Turing machine can be simulated by a constant-bit-size looped transformer with head–layer product $K = 8kk'$ and context window length $O(s(n)/L)$, taking $O(s(n)^{1/k}/L)$ CoT steps for each simulated TM step, for a total CoT length of $O(t(n) \cdot s(n)^{1/k}/L)$, for every loop count $L = L(n)$ and fixed integer $k \geq 1$ with $s(n)^{1/k} = \Omega(L)$.

Resource Accounting

Concrete instance: For $s(n) = m^2$, $k = 2$, $L = \Theta(m)$ (admissible since $s(n)^{1/k} = m = \Omega(L)$):

• $O(t(n))$ generated tokens
• $O(m)$ visible window positions
• $\Theta(m^2)$ cached entries
• $O(t(n)m)$ loop executions

Worked Example (Section 4.5)

For one queue with $L = 3$, $\ell = 7$, $w = 3$:

Softmax Extension (Section 5)

The construction holds under a max-first binary32 softmax kernel:

Lemma 5.1: If a score row has unique maximizer $j^*$ with score gap at least 256, then the max-first kernel's computed attention output is exactly $v_{j^*}$, independently of row length.

Corollary 5.2: Setting $\Delta = 256$ in Section 4.2, every score row has scores in {256, 0}, a unique maximizer at distance $w_r - 1$, and shifted losers exactly −256, all exactly representable in binary32. Theorem 4.3 and Proposition 4.2 hold with softmax attention under this kernel.

Theoretical and Practical Implications

Theoretical Significance

1. Interpolation result: The construction shows explicit CoT and latent thought are not fundamentally different capabilities but two placements of the same general-purpose computation realized by recurrence.
2. Resource trade-off: The loop count $L$ is the "exchange rate" between external trace and internal computation—decreasing $L$ externalizes computation as tokens; increasing $L$ folds consecutive CoT steps into each token as latent iterations.
3. Layer alignment: The key insight is that queue fronts must sit in the cache at the iteration that consumes them—a "layer-aligned" representation.

Practical Messages for Real LLMs (Conjectural)

• Looped transformers can internalize substantial parts of CoT into recurrent state, preserving general-purpose computation while separating reasoning from visible tokens.
• Generated CoT token count need not measure serial computation—one token can summarize $L$ consecutive steps.
• Learning difficulty at large $L$: The explicit trace becomes strided (only every $L$-th state is emitted), so intermediate latent steps are not supervised by next-token prediction, potentially making such computation difficult to acquire from pretraining alone.
• Design suggestion: Take the loop count as an explicit budget for latent computation and supervise only selected boundary states.

Conclusion

This paper constructs constant-bit-size looped transformers that simulate Turing machines with both context window and CoT length reduced by a factor of $L$ relative to unlooped queue-machine simulations. The construction interpolates between explicit CoT (at $L = 1$) and increasingly latent thought (at larger $L$), with the loop count serving as the exchange rate between visible tokens and internal computation.

Key Limitations

• Loaded cache: Input is pre-loaded into the initial KV cache; initialization cost is excluded from bounds.
• Visible resources only: The factor-$L$ reduction applies only to generated tokens and visible window; total cached KV state and serial block work are unchanged.
• Kernel-conditional softmax: Results hold only under the specific max-first binary32 contract.
• No learning claims: Nothing shows such computations are learned by pretraining or other training signals.
• Bounds, not measurements: All quantitative statements are asymptotic bounds; no experiments were performed.

Future Directions

• Understanding how looped architectures can be trained to internalize reasoning steps
• Investigating supervision strategies for strided traces
• Exploring the relationship between loop count and learning difficulty in practical models