Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
For researchers working on Transformer reasoning and length generalization, this work clarifies fundamental limitations and provides a constructive solution to overcome them.
The paper identifies that Transformers with Chain-of-Thought cannot length-generalize beyond TC^0 under standard positional encodings and finite alphabet, but allowing the vocabulary to grow with problem size enables length-generalizable Turing machine simulation with linear CoT trace length. Empirical results show that using signpost tokens and value change encodings improves length generalization on hard problems.
Chain-of-Thought (CoT) has been shown to empirically improve Transformers' performance, and theoretically increase their expressivity to Turing completeness. However, whether Transformers can learn to generalize to CoT traces longer than those seen during training is understudied. We use recent theoretical frameworks for Transformer length generalization and find that -- under standard positional encodings and a finite alphabet -- Transformers with CoT cannot solve problems beyond $TC^0$, i.e. the expressivity benefits do not hold under the stricter requirement of length-generalizable learnability. However, if we allow the vocabulary to grow with problem size, we attain a length-generalizable simulation of Turing machines where the CoT trace length is linear in the simulated runtime up to a constant. Our construction overcomes two core obstacles to reliable length generalization: repeated copying and last-occurrence retrieval. We assign each tape position a unique signpost token, and log only value changes to enable recovery of the current tape symbol through counts circumventing both barriers. Further, we empirically show that the use of such signpost tokens and value change encodings provide actionable guidance to improve length generalization on hard problems.