# Internalizing Chain-of-thought into Looped Transformers

> Looped transformers can simulate Turing machines with both context window and chain-of-thought length reduced by a factor L, trading external tokens for internal recurrent computation.

- **Source:** [arXiv](https://arxiv.org/abs/2610.25998)
- **Published:** 2026-10-31
- **Permalink:** https://picx.dev/p/rwn3Nh
- **Whiteboard:** https://picx.dev/p/rwn3Nh/image

## Summary

## 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

| Quantity | $L = 1$ (endpoint) | Admissible $L = O(s(n)^{1/k})$ |
|---|---|---|
| Generated tokens | $O(t(n)s(n)^{1/k})$ | $O(t(n)s(n)^{1/k}/L)$, exactly $\lceil \tau(n)/L \rceil$ |
| Visible positions (window) | $O(s(n))$ | $O(s(n)/L)$ |
| 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 |

**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$:

| Pass $i$ | Window | Steps executed | Reads ($l = 0, 1, 2$) | Emits |
|---|---|---|---|---|
| 2 | {0, 1, 2} | 6, 7, 8 | $\sigma_0, \sigma_1, \sigma_2$ (at pos. 0) | $(q_9, \sigma_9)$ |
| 3 | {1, 2, 3} | 9, 10, 11 | $\sigma_3, \sigma_4, \sigma_5$ (at pos. 1) | $(q_{12}, \sigma_{12})$ |
| 4 | {2, 3, 4} | 12, 13, 14 | $\sigma_6, \sigma_7, \sigma_8$ (at pos. 2) | $(q_{15}, \sigma_{15})$ |

### 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

---

_Markdown view of https://picx.dev/p/rwn3Nh, served by PicX — AI-generated visual whiteboard summaries of research papers._