Internalizing Chain-of-thought into Looped Transformers

The expressive power of transformers concerns both what they can compute and the resources required, including depth, precision, context length, and generated tokens. We organize existing constructions by where they store intermediate states. *In-layer* constructions keep them in hidden activations and produce the answer in one generation step, whereas *in-CoT* constructions record the computation in generated tokens and keep the workspace in the context window. We construct a family of constant-bit-size looped transformers that interpolates between these two classes. For a prescribed loop count $L=L(n)$ and a fixed integer $k\ge 1$ satisfying $s(n{)}^{1/k}=\Omega (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 the finite-precision softmax kernels specified in this paper.