- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper explores two existing paradigms of chain-of-thought reasoning, implicit and explicit CoT, specifically in linear self-attention transformers. Both approaches have been studied in previous work to understand the settings in which they can be useful. This paper brings these approaches into a unified framework and compares their expressivity on two tasks, i.e. weight prediction and query prediction.
The paper first recovers the previously known results that explicit CoT can implement multi-step gradient descent for weight prediction, while implicit CoT can do so for query prediction with a sign correction. More importantly, the authors establish new negative results showing implicit CoT cannot implement the same multi-step GD trajectory for weight prediction, and explicit CoT cannot implement even a single GD step for query prediction under their respective formulations.
They attribute these limitations to context overwriting in implicit CoT and limited writable state in explicit CoT. This motivates introducing an additional scratchpad that allows both methods to overcome these limitations. The authors provide theoretical results on expressivity, training convergence and generalization, including results supporting the scratchpad constructions, along with experiments on linear regression and nonlinear LEGO tasks to support their findings
Critical strengths
(1) The paper brings together two existing paradigms. These are often studied separately, so evaluating them in a unified framework is interesting. More importantly, this comparison highlights the role of scratchpads in overcoming their different limitations, which could potentially help with designing future architectures.
(2) The math is quite comprehensive, and the experiments are selected appropriately to highlight the differences between the methods.
Critical weaknesses
(1) The paper in general seems to overstate the significance and novelty. The positive results for implicit and explicit CoT in their respective settings are largely from existing works, and the primary new theoretical contributions are the negative results. However, I am not sure how surprising these results are given that the two methods operate quite differently, and the failures depend on specific choices of input encoding and architecture. In particular, it is not clear why we should expect either method to work in a setting designed around the other in the first place. While the negative results are interesting for highlighting their differences, I am not sure how much broader insight they provide. I think the most interesting contribution is showing how scratchpads can overcome these different limitations within the same framework. More emphasis should be put on these. Scratchpads improving transformers is not an entirely new concept, so experiments need to meaningfully highlight this.
(2) The paper is quite heavily limited to the linear self-attention setting. The authors mention that some results can be extended to regular softmax attention, and provide an additional LEGO experiment with softmax and the scratchpads. However, the evidence (experimental or theoretical) stating that the GD phenomenon carries over to softmax in some shape or form even if not strictly is either not there or does not receive enough emphasis. More direct experiments addressing the softmax setting are either not present or not appropriately emphasized.
Questions for authors
(1) What are the main new insights from the negative results? What broader implications do these results have, in particular what is new about the scratchpad construction compared to previous work?
(2) Do the authors expect the GD phenomena to carry over to regular softmax transformers? Can you provide direct experiments on weight and query prediction with softmax attention to support this?
A1: Thank you for this insightful comment. We agree that we should state the scope and novelty of contributions more carefully. We would like to clarify that only two of the eight settings in our comparison come from prior work: explicit CoT for weight prediction with a scratchpad, following [1], and the looped transformer for query prediction without a scratchpad, following [2]. We will clearly identify these two cases as existing results rather than contributions of this work. The remaining six settings complete the comparison across model formulation, task, and embedding dimension. For the four successful cases, we provide constructive expressivity results and corresponding training guarantees. For the two failure cases, we provide expressivity lower bounds showing that the target GD updates cannot be exactly implemented under the specified encodings. We believe the main contribution is not any individual case, but the systematic upper- and lower-bound characterization across these eight controlled settings.
We also agree that the general usefulness of scratchpads is already known and is not itself our contribution. Our contribution is to characterize the representation capacity provided by a scratchpad within a controlled theoretical framework. We believe that our results are more appropriately framed as upper- and lower-bound results for looped transformers and transformers with CoT under different embedding dimensions. In fact, we believe our analysis can lead to matching upper and lower bounds in each case. We will revise the paper accordingly.
Regarding the broader implications, since our work is theoretical and focuses on a controlled setting, we believe its implications are most direct for areas such as AI for Science, where linear attention mechanisms are often considered [3] and where models are expected to learn tasks that may also be addressed by classical numerical algorithms. For these tasks, our work suggests that scratchpad-like hidden dimensions may serve as an important computational resource, enabling transformer models to emulate certain iterative algorithms more efficiently.
A2: We conduct softmax attention experiments on all eight combinations of task, model formulation, and embedding. We find that under our controlled architecture and training protocol, none of the eight configurations recovers the multi-step GD trajectory. These results suggest that the behavior observed with linear attention does not transfer directly to softmax attention in our setting. We will include these experiments in the revised work.
[1] Huang et al. Transformers learn to implement multi-step gradient descent with chain of thought. ICLR 2025.
[2] Gatmiry et al. Can looped transformers learn to implement multi-step gradient descent for in-context learning? ICML 2024.
[3] Cao, Choose a transformer: Fourier or galerkin. NeurIPS 2021.