A Tight Hierarchy for Chain of Thought
A provable increase in reasoning steps lets transformers solve problems beyond their previous computational reach.
Thanh Le, A. Pavan and N. V. Vinodchandran establish what they describe as the first hierarchy theorem for chain-of-thought computation. For any reasonable step bound \(r(n)\geq n\) and any \(\varepsilon>0\), allowing \(O(r(n)^{1+\varepsilon})\) steps strictly expands the class of solvable decision problems over \(O(r(n))\) steps. The proof combines known simulations between transformers and Turing machines with a padding technique implemented within the transformer model. The result concerns computational power under formal resource bounds.
ArXiv · AI/CL/LG's note
Thanh Le, A. Pavan and N. V. Vinodchandran establish what they describe as the first hierarchy theorem for chain-of-thought computation. For any reasonable step bound \(r(n)\geq n\) and any \(\varepsilon>0\), allowing \(O(r(n)^{1+\varepsilon})\) steps strictly expands the class of solvable decision problems over \(O(r(n))\) steps. The proof combines known simulations between transformers and Turing machines with a padding technique implemented within the transformer model. The result concerns computational power under formal resource bounds.
ArXiv · AI/CL/LG's note
score 5