Search papers, labs, and topics across Lattice.
This paper investigates the length generalization capabilities of Transformers using Chain-of-Thought (CoT) reasoning, finding that standard Transformers with CoT are limited to $TC^0$ when generalizing to longer CoT traces with a fixed vocabulary. To overcome this limitation, the authors propose a novel architecture using signpost tokens and value change encodings, which allows for a length-generalizable simulation of Turing machines with a vocabulary that grows with problem size. Empirically, they demonstrate that these techniques improve length generalization on challenging problems.
Chain-of-Thought reasoning in Transformers hits a surprising expressivity ceiling when generalizing to longer sequences, unless you let your vocabulary grow with the problem size and use "signpost" tokens.
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.
