Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective

Summary

The paper mainly focuses on theoretically proving the effectiveness of the CoT in autoregressive Transformer models for solving fundamental mathematical and decision problems through generating intermediate steps. It demonstrates that any finite-depth Transformer model cannot directly output correct answers to these tasks unless the model size grows super-polynomially with the input length. The paper also includes experimental validation using a constructed dataset.

Strengths

1. The paper provides a solid theoretical proof of the effectiveness of CoT, making a valuable contribution to further exploring the underlying mechanisms of CoT operation. 2. The theoretical proofs presented in the paper are comprehensive and well-organized. 3. The research problem addressed in the paper is clearly significant. CoT has shown strong empirical performance but lacks theoretical analysis. Thus, this study is timely and necessary.

Weaknesses

1. The experimental section seems to be insufficient, for example, the length extrapolation experiment only provides results for one task. 2. The exploration of model architectures is lacking. (see my questions)

Questions

1. Is there a specific reason for choosing autoregressive Transformer? Were other models, such as the encoder-decoder architecture like T5 model be considered? Would CoT be equally effective in those models? 2. In the experiments, a Transformer with three layers achieves near-perfect accuracy on each task, but the proofs utilize five layers. How much does the number of layers affect the performance of CoT, and are there necessary layer numbers for different tasks? Additionally, the difficulty of the datasets for now seem insufficient to explore this question. 3. In the Length Extrapolation section, only Arithmetic Expression Extrapolation is explored. Does CoT also possess the ability to learn the underlying mechanisms for other tasks? The conclusion seems to lack sufficient experimental verification and analysis. 4. Have you considered the impact of the quality of intermediate steps on the performance, such as inserting some invalid intermediate steps or omitting a certain number of intermediate steps?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

Section 7 of the paper provides a thorough discussion of the limitations. Additionally, while CoT demonstrates excellent performance across various tasks, this paper mainly focuses on mathematical tasks and could further explore other types of tasks, such as logic reasoning tasks represented in natural language.

Summary

The paper contributes to theoretical and empirical understanding of Chain-of-thought, i.e. intermediate process generation to assist desired output generation. In the theory part, authors show - log-presicion Transformer with bound depth cannot solve simple math tasks (calculate, solve linear equations) unless the model size grows super-polynomially w.r.t. input length. the proof is based on circuit complexity and a bottleneck of parallel complexity (assuming $TC^0 \neq NC^1$). However, constant-size Transformer can solve both by generating common math intermediate steps. - for dynamic programming (DP), Transformers with CoT can generate the correct answer intuitively. In contrast, it is proven that Context-Free Grammar Membership Testing cannot be solved with a bounded-depth Transformer with polynomial depth. Experiments then validate these results using two math and two DP tasks, showing CoT > no CoT (with more layers even).

Strengths

- CoT has been important in language processing, and its theoretical and empirical understanding is important and timely. - As far as I can tell, both the theory and experiment parts of the paper is solid, and well-written. - I like the connection to circuit complexity theory. Though the conclusion and "intuition" is not hard to grasp, the theory part is technical and non-trivial to establish.

Weaknesses

- As noted by authors, it's still limited to expressivity (not learning with large corpora, large model). - Some missing references around Dyck language recognition: Self-attention networks can process bounded hierarchical languages. ACL 2021 RNNs can generate bounded hierarchical languages with optimal memory. EMNLP 2020

Questions

- Seems "Self-attention networks can process bounded hierarchical languages" proved that (2-layer) Transformers can recognize Dyck, yet this papers proves CFG recognition is in general hard? Some discussion would be nice. - Would results hold for RNN or other architectures? Some discussion would make the paper stronger.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

Authors write about limitations fairly.

Summary

This paper presents various separation results, showing that a Transformer with CoT can solve certain formally-defined reasoning tasks, but a Transformer *without* CoT cannot (assuming bounded depth). This sheds light on the power of CoT. The formal results are supplemented with empirical results that support the claims.

Strengths

- Understanding CoT is an important and timely question. This paper is therefore tackling a significant question. - To the best of my knowledge, this is the first paper to provide a theoretical explanation of the power of CoT (i.e., originality). - In general, the paper is quite clear and high-quality, though I think the notation could be improved (see below).

Weaknesses

- I think calling it CoT but focusing on "CoT generation" is perhaps misleading. Many people think of CoT as a prompting technique. In my opinion, the generation aspect that this paper focuses on is actually bigger/more important than CoT suggests, and I actually think that - although buzzwordy - CoT diminishes the general power of generation that this paper is getting at (i.e., this paper transcends CoT). I would suggest looking into alternative, more general titles. - Section 4.1 has a lot of notation, including double subscripts. I think there's a significant lack of accessibility created by the heavy notation. I would really encourage the authors to think about whether the notation could be simplified. I think doing so could substantially increase the long-term impact of this paper. - Relatedly, equations (4) and (5) would be clearer if their new objects were introduced and explained conceptually before jumping into equations (4) and (5). - Overall, I think the paper could do a better job explaining the significance of the theoretical results. Although this is an important problem to study theoretically, and this paper does a good job of initiating that study, it's not entirely clear what can be gained conceptually from this analysis. I think many people already intuitively grasp that generating more tokens gives an LLM more power, and various methods that allow more tokens to be generated before arriving at a final answer are more powerful. It would be nice to understand whether there's a conceptual message here that goes any deeper than the aforementioned intuition.

Questions

- See CoT naming comment above. Do you agree? - See notation comment above. Is there a way to simplify the notation in Section 4.1? Is there a reason it has to be this complicated? If it seems necessary, maybe there's a simpler version that can be presented in the body of the paper, with the full version moved to the appendix? - My main question is also discussed in the Weaknesses section. Is there any conceptual takeaway from this theoretical analysis beyond "generating more tokens is more powerful"? Even without that, I think this is a strong paper. However, I think this could be an especially powerful paper if the intuitions from the theoretical analysis could be further synthesized in this direction (and made accessible to readers).

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors do a nice job of discussing some of the limitations of this work. There is no discussion of societal impact, but I do not think this is a problem for this particular paper.

Summary

This paper studies the theoretical power of the Chain-of-Thought (CoT) prompting. In particular, this paper mathematically confirms that two well-chosen tasks (e.g., arithmetic and equation) and the problem of Dynamic Programming are beyond bounded-depth Transformer models without CoT (unless their size grows prohibitively large); with CoT and generated intermediate derivations, those problems become solvable. The mathematical derivations are under mild assumptions, and empirical results confirms the mathematical study (on four representative tasks).

Strengths

Given the prevalence of CoT, theoretical study of the limit of CoT becomes extremely valuable. This paper overcomes several limits in previous studies (e.g., assuming infinite precision) and focuses on the setting of autoregressive Transforms, which is close to the scenario of real-world LLMs. Moreover, the proposed empirical tasks are illustrative and easily reproducible.

Weaknesses

I don't find any noticeable weakness in this paper.

Questions

Line 245, the success of solving Dynamic Programming problems critically depends on the input sequences being laid out in a topological order. In the two DP experiments (Longest Increasing Subsequence and Edit Distance), the topological order appears to be learnable from the CoT dataset. Could there be any theoretical study about how hard it is to learn this order?

Rating

9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors have adequately addressed the limitations.

Thanks

Thanks! Would be nice to see these incorporated into the revision.

Thanks

Thank you very much for the detailed and enlightening reply! I really appreciate the analysis.