首个思维链层级定理：更多 CoT 推理步数可证明带来更强计算能力
A Tight Hierarchy for Chain of Thought
数学味很浓的一篇理论论文，首次证明了思维链步数是种基础计算资源，多用步数确实变强，不是玄学。
arXiv 论文《A Tight Hierarchy for Chain of Thought》建立了首个针对 CoT 计算的层级定理。结果指出，对任意资源上界 r(n)≥n 和任意 ε>0，CoT(r(n)) 是 CoT(r(n)^(1+ε)) 的真子集，即增加 O(r(n)) 量级的 CoT 推理步数可严格提升 transformer 的计算能力。证明不依赖经典的对角化方法，而是借助 CoT 增强型 transformer 与图灵机之间的双向模拟，把复杂度理论中的 padding 技巧移植到 transformer 模型中，得到紧致层级。
A Tight Hierarchy for Chain of Thought
Chain-of-thought (CoT) reasoning has emerged as a powerful paradigm for extending the computational capabilities of transformer-based models. A growing body of recent work has begun to uncover the fine-grained computational power of transformers augmented with CoT, as well as their connections to classical complexity theory. In this work, we advance this line of research by establishing the first hierarchy theorem for CoT-based computation. Our main result shows that for any reasonable resource bound $r(n) \geq n$ and any $\varepsilon > 0$, \[ \mathrm{CoT}(r(n)) \subsetneq \mathrm{CoT}(r(n)^{1+\varepsilon}), \] where $\mathrm{CoT}(r(n))$ denotes the class of decision problems solvable by transformers using $O(r(n))$ CoT reasoning steps on inputs of length $n$. Our result shows that increasing the number of CoT reasoning steps provably yields strictly greater computational power, establishing CoT steps as a fundamental resource in transformer-based computation. Unlike classical hierarchy theorems, which are typically proved via diagonalization, our approach leverages known coarse-grained simulations between CoT-augmented transformers and Turing machines in both directions. Building on these connections, we adapt the classical padding technique from complexity theory to this setting to obtain a tight hierarchy. A key technical contribution of our work is the implementation of padding within the transformer-based CoT model.
