对比两种推理方法：循环变压器适合确定性任务，思维链适合组合问题近似推理。
To CoT or To Loop? A Formal Comparison Between Chain-of-Thought and Looped Transformers
- 循环变压器可高效模拟确定性任务的并行计算
- 思维链配合随机解码在组合问题上表现更优
- 为选择推理范式提供理论依据，适合不同任务
思维链（CoT）和循环变压器在推理任务中均被实证提升性能，并理论上通过递归增加计算步骤增强表达能力。然而其比较能力尚不明确。本文进行形式化分析，发现循环变压器能高效模拟确定性任务的并行计算，可形式化为有向无环图上的求值；而带有随机解码的思维链在组合结构的近似推理中表现更优，即自可约问题。这些差异揭示了深度递归更适合的任务类型，为选择推理范式提供实用指导。
原文摘要 · Abstract (English)
Chain-of-Thought (CoT) and Looped Transformers have been shown to empirically improve performance on reasoning tasks and to theoretically enhance expressivity by recursively increasing the number of computational steps. However, their comparative capabilities are still not well understood. In this paper, we provide a formal analysis of their respective strengths and limitations. We show that Looped Transformers can efficiently simulate parallel computations for deterministic tasks, which we formalize as evaluation over directed acyclic graphs. In contrast, CoT with stochastic decoding excels at approximate inference for compositional structures, namely self-reducible problems. These separations suggest the tasks for which depth-driven recursion is more suitable, thereby offering practical cues for choosing between reasoning paradigms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。