acceptodds
Under review as a conference paper at ICLR 2027

Internalizing Chain-of-thought into Looped Transformers

Abstract

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 and a fixed integer satisfying , our transformer simulates a time-, space- Turing machine using a context window of and generated tokens, reducing both resources by a factor of relative to the corresponding unlooped queue-machine simulation. The construction also holds with the finite-precision softmax kernels specified in this paper.

Primary area:
learning theory
Keywords:
Expressivity of transformers, Looped transformers, Chain-of-thought, Turing-completeness

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_xCV2OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper builds directly on two prior works by Li & Wang (2025a,b), which convert Turing machines into (multi-)queue machines and then simulate those with CoT transformers. The present work shows that in this multi-queue simulation, looped depth can be traded for CoT length, i.e., looping the same decoder layer LL times for each token reduces CoT length by a factor of LL. Here, LL can be a function of the input length, but has to be bounded by O(s(n)1/k)O(s(n)^{1/k}) where s(n)s(n) is the simulated Turing Machine's space usage. Moreover, the authors turn the hardmax construction into a finite-precision softmax one by relying on underflow.

Critical strengths

The paper gives a clear theoretical example where looped depth can be traded for CoT length up to some point. It is cleanly explained that this tradeoff can only be done up to depth L=O(s(n)1/k)L=O(s(n)^{1/k}), and that other CoT Turing machine simulation results that do not work via queue machines do not admit such a looped construction in a straightforward way, which I agree with.

Critical weaknesses

The paper is quite specific to the prior queue-machine constructions, and my understanding of it relied heavily on being familiar with these prior works. As the authors say themselves, the conversion to looped depth is also specific to these queue-machine constructions, and it remains unclear to what extent this tradeoff can be obtained in other constructions. The main problem with that is that these queue-machine constructions, and hence also the construction in this work, use non-standard transformer architectures, namely with input-dependent positional encodings that make each head attend to a fixed offset instead of using queries and keys for context-dependent retrieval.

Moreover, the benefit of the depth vs. CoT-length tradeoff is somewhat overclaimed in the abstract and introduction, using phrasings like "...reducing both resources by a factor of LL...". This sounds like the looped depth achieves some efficiency gain, while in reality the KV cache is merely reshaped, with its total size staying at the optimal floor O(s)O(s) achieved by the prior queue-machine constructions regardless of LL. I believe that the paper should be reframed accordingly and not claim any efficiency advantages, except for the actual compute operations with quadratic attention, in which case increasing depth and reducing CoT length by the same factor is an advantage.

Lastly, the "Potential Messages for Real LLMs" paragraph overreaches in the third and fourth points, while the second point basically says that the layers of a model can be used for serial computation, which is obvious.

Questions for authors
  1. If I understand correctly, the KV cache in your construction is initialized in a specific way that is not obtained through the model's actual forward pass. Could the model be adapted to perform this prefill itself instead, as is commonly the case?
  2. As in the prior queue-machine constructions, the positional encoding, and here also the maximally usable depth L(n)L(n), depend on the input through the space usage of the simulated Turing machine on that input. This space usage s(n)s(n) has to be known a priori, which is a clear disadvantage compared to, e.g., PENCIL (Yang et al., 2025), where the optimal context length is achieved by dynamically dropping context without prior knowledge of the required space. Do you think there is a path to achieving the same in your queue constructions, in particular choosing the looping depth dynamically during execution instead of fixing it beforehand?
Reviewer_63xCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper distinguishes two ways transformer computations store intermediate state: in-layer constructions, which keep state in hidden activations and answer in one step, and in-CoT constructions, which record state in generated tokens and keep the workspace in the context window. The main result is a family of constant-bit-size looped transformers that interpolate between the two regimes: applying one shared decoder block repeatedly for each generated token lets the model simulate a time- and space-bounded Turing machine with a smaller context window and fewer generated tokens, both resources shrinking in proportion to the loop count relative to the unlooped queue-machine simulation. The key device is a layer-aligned reorganization of the queue representation so that everything a recurrent step needs is available in the matching cache layer. The construction is also shown to hold under a finite-precision softmax kernel. The paper closes with speculative remarks on implications for real reasoning models.

Critical strengths
  1. The layer-alignment observation correctly identifies why folding chain-of-thought into a loop is not merely cosmetic (the cross-layer access restriction) and solves it.
  2. Proving exact hard-selection emulation under a production-style binary32 softmax kernel closes a gap left by constructions that assume exact real arithmetic, at constant precision.
Critical weaknesses
  1. The loop-count-one endpoint is exactly the prior queue-machine result; the novelty is only a constant-factor resource improvement from grouping. The paper offers a useful unification but changes nothing in the expressive-power landscape: no new upper or lower bounds, no new complexity-class separation.
  2. The initialization preloads the execution log directly into the KV cache, a non-standard way to encode input. Stating the assumptions under which this could be relaxed to a standard input encoding without harming the asymptotics would strengthen the paper.
  3. The "implications for real LLMs" discussion is loosely tied to the theorem, which is a construction result with hand-designed weights and says little about learnability in trained models.
  4. The paper does not address whether the resource reduction is optimal or whether context can be compressed further under the same model.
Questions for authors
  1. Can the initialization be relaxed to a standard input encoding (e.g., the input string on a tape, embedded as an ordinary token sequence) without changing the asymptotic window and CoT bounds? If so, what is the precise statement?
  2. The bit-size is constant but involves constants depending on the number of states, the alphabet size, and the number of queues. For the machines actually used, how large are these constants, and does this meaningfully affect "constant bit-size" as a practical notion?
  3. Is the layer-alignment technique specific to queue machines, or does it extend to any construction whose read/write structure admits a stride decomposition? A brief necessary/sufficient condition would raise the paper's generality.
  4. Is there a matching lower bound (even heuristic) showing the window/CoT tradeoff is optimal?
Reviewer_ouGgOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper investigates the tradeoff between internal computation and explicit CoT in looped transformers. Building on Li and Wang (2025b), the authors construct a constant-bit-size looped transformer that reduces both generated CoT tokens and visible context length by a factor of LL while preserving Turing-machine simulation capabilities. The result is also extended to a specified finite-precision softmax implementation.

Critical strengths
  1. The paper establishes explicit tradeoffs between loop iterations, generated CoT length, and visible context length while maintaining constant bit-size. This provides a more resource-constrained theoretical guarantee than some existing latent-reasoning results.
Critical weaknesses

1. Unclear novelty and significance relative to prior work.

The proposed construction appears closely related to Li and Wang (2025b). The main difference seems to be the use of looped transformers to perform multiple computational steps before generating each token, together with a mechanism for aligning KV-cache access. Since the idea of replacing explicit CoT steps with recurrent computation has already been studied, it is unclear how substantial the new contribution is beyond combining existing techniques. A direct comparison with Li and Wang (2025b), preferably with a figure illustrating the technical differences and the nontrivial parts of the new construction, would help clarify the novelty and significance.

2. Unclear presentation and insufficient motivation.

The paper is difficult to follow, particularly in identifying the main research question, why it matters, and how the proposed construction addresses it.

  • Notation and readability: Some notation is used without sufficient explanation (e.g., (n), s(n) in the abstract, and (w_r) in line 304, which is central to the construction, is used before its definition). Moreover, (k) denotes the simulation parameter in the main theorem, the number of TM tapes in sec 3.1, and the execution-log index in def 1. Similarly, (K) denotes the head–layer product in the table 1 footnote but the number of queues in sec 3.1. Although these uses can be distinguished from context, they make the paper unnecessarily difficult to follow. Prevent overloading of notation and add a notation table will improve readability.

  • Connection to practical LLMs: The "Potential Messages for Real LLMs" subsection lists several implications for practical reasoning models. However, the connection between these claims and the formal results is not sufficiently established. In particular, the discussion of pretraining and reinforcement learning appears speculative, since the paper studies a theoretical construction rather than the learning behavior of practical models. The authors should clarify which implications follow directly from their theorem and which are conjectures or potential directions for future work. These presentation issues make it difficult to assess the importance of the theoretical contribution, especially given its close relationship to existing work.

Questions for authors
  1. What does RASP stand for in line 31? I assume it refers to the framework introduced in Thinking Like Transformers (Weiss et al., 2021). Although established in Transformer expressivity research, it may not be familiar to the broader ICLR audience. A brief definition would improve readability.

  2. The paper reduces the visible context length and generated CoT tokens by a factor of (L), but the total KV-cache storage and serial computation remain asymptotically unchanged. Why is this tradeoff theoretically significant beyond reorganizing the same computation?

  3. thm 5 assumes a pre-initialized KV cache. Does the theorem also require s(n)≥ns(n)\geq n? How should the cost of KV-cache initialization be accounted for when interpreting the claimed context-length reduction?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.