To CoT or To Loop? A Formal Comparison Between Chain-of-Thought and Looped Transformers

Understand

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.