Why CoT is the key: classic paper shows transformers need it for serial problems
willcb · x · 2026-10-16
willcb recommends one of his favorite modern papers: "Chain of Thought Empowers Transformers to Solve Inherently Serial Problems" by Li, Liu, Zhou, and Ma (Stanford/Google).
Core results:
- Constant-depth transformers with finite precision can only solve problems in TC⁰ (tightened to AC⁰ with constant-bit precision) without CoT, lacking inherent serial computation;
- With T steps of chain of thought, constant-depth transformers with O(log n) embedding size can solve any problem solvable by boolean circuits of size T;
- Empirically, CoT dramatically improves accuracy on parallel-hard tasks like permutation group composition, iterated squaring, and circuit value problems, especially for low-depth models.
The poster argues it "basically fully explains why transformers won, and why RL emerges as the right algorithm for the architecture."
Related event: CoT Theory Paper Praised for Explaining Why Transformers Win(2 posts)→
More from Research
- UCSD Researchers Propose Dataset Watermarking Detectable via Black-Box API Access — yuxiangw_cs · 2026-10-16
- EmbodiedEvo tops RoboDojo as agents inherit reusable skills and lessons — Aiden_Tech_Ai · 2026-10-16
- CHI reviewer laments: papers' Discussion sections now cite nothing — IanArawjo · 2026-10-16
- Casper: Understanding 90% of neurons ≠ understanding the network — StephenLCasper · 2026-10-16
- NVIDIA Launches cuPotential in CUDA-X to Bring AI Agents to Semiconductor Materials Simulation — tomaszbednarz · 2026-10-16
- Agentic Search Systems Are Rewarded Only for Final Answers, Raising Faithfulness Concerns — burkov · 2026-10-16