- 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 times for each token reduces CoT length by a factor of . Here, can be a function of the input length, but has to be bounded by where 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 , 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 ...". 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 achieved by the prior queue-machine constructions regardless of . 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
- 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?
- As in the prior queue-machine constructions, the positional encoding, and here also the maximally usable depth , depend on the input through the space usage of the simulated Turing machine on that input. This space usage 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?