arXiv preprint ·
Internalizing Chain-of-thought into Looped Transformers
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
A 55-Addition Rank-23 Scheme for $3\times3$ Matrix Multiplication via Exact Two-Sided Minimization
Bidirectionality is Necessary in Cellular Machines for Exact-Arrival Multi-Agent Path Finding
Fixed Sets and the Hardness of Computing Correlated Equilibria
Orienting mixed graphs for reachability pairs: When the all pairs setting is easier than the general one
Subjective Valuations Make It Hard to be Fair: The Complexity of Resource Allocation to Groups of Agents
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.