Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
Oliver Kraus, Yash Sarrof, Yuekun Yao, Alexander Koller, Michael Hahn, Saarland University · 2026
Read Barriers to Universal Reasoning With Transformers (And How to Overcome Them) by Oliver Kraus, Yash Sarrof, Yuekun Yao, Alexander Koller, Michael Hahn, Saarland University (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-25800.txt.
Introduction
Kraus and four colleagues test whether transformers with chain-of-thought reasoning generalize to traces longer than training traces. Chain-of-thought boosts scores and, in theory, grants Turing completeness. With standard positional encodings and a finite alphabet, however, length-generalizable transformers stay within a restricted circuit class. Letting vocabulary grow with problem size restores a length-generalizable Turing simulation, with trace length linear in runtime. Unique signpost tokens per tape position and value-change logging beat copying and retrieval barriers, with empirical backing.
Catalog record
| CREATOR | Oliver Kraus, Yash Sarrof, Yuekun Yao, Alexander Koller, Michael Hahn, Saarland University |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95822 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.25800
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Barriers to Universal Reasoning With Transformers (And How to Overcome Them) Oliver Kraus, Yash Sarrof, Yuekun Yao, Alexander Koller, Michael Hahn, Saarland University Abstract 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 \textbf{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. 1 Introduction Chain of Thought (CoT) empirically improves the performance of Transformers ( 52 ) on reasoning tasks ( 55 ; 39 ; 26 ; 10 ) . This apparent increase in reasoning capability has been explained by theoretical findings showing that any Turing Machine (TM) can be simulated by a Transformer with CoT ( 41 ; 4 ; 55 ; 35 ; 42 ) , whereas Transfomers without CoT are restricted to the complexity class \textbf{TC}^{0} ( 34 ) . However these results point only to the existence of such a simulation, but not to whether such a simulation can be learned from finite CoT traces. Indeed, a mounting body of empirical evidence shows that the accuracy of Transformers degrades sharply with CoT lengths – across tasks including algorithmic ( 3 ; 14 ) , logical ( 23 ; 44 ; 45 ; 46 ) , planning ( 49 ) , and symbolic reasoning ( 37 ; 7 ) . This behavior is poorly understood from a theory perspective. Here, we study this question using recent advances in the theory of Transformer length generalization, specifically C-RASP ( 57 ; 16 ) and C*-RASP ( 47 ) and make two complementary theoretical contributions. In our first key result , we prove that under standard positional encodings and a finite alphabet, Transformers even with CoT will likely length-generalize only on problems within \textbf{TC}^{0} , even when they are trained to perform CoT reasoning. We show this by proving that any task (input and CoT trace) expressible in C-RASP , is also definable in \textbf{TC}^{0} , strengthening the result of 21 which showed that C-RASP CoTs are not Turing complete. This is a surprising discovery, as prior work ( 9 ; 35 ; 28 ) attributes the success of CoT to transcending the \textbf{TC}^{0} barrier. While this is true for expressivity, we find it to be not true for the stricter requirement of length generalization. Two barriers impede length-generalization of Turing-complete reasoning with Transformers: copying arbitrary strings, and position-based retrieval (cf. Figure 1 ), both challenging for length generalization ( 29 ; 58 ; 8 ; 16 ; 22 , e.g.) . We address copying limitations using signpost tokens , and circumvent retrieval limitations by a novel CoT scheme encoding the values of a tape cell before and after a computation step changing it. This construction allows us to encode the individual CoT steps in C*-RASP (extension of C-RASP to infinite alphabets). 47 shows that, under a idealized learned model and with an infinite alphabet, Transformers provably length generalize on problems describable in C*-RASP . Thus, in our second key result we prove that Transformers with CoT can length-generalizingly learn to simulate any TM if they (a) get to use an infinite alphabet of signpost symbols and (b) the computations of the TM are encoded in the CoT in the right way. We also attempt to empirically validate our theoretical predictions. We find that Transformers trained from scratch do not length-generalize in CoT reasoning on Parity, Boolean Evaluation, and Permutation, but a signpost symbol inventory growing with instance size and a value-change format can boost length-generalization. These insights help get better prompting performance on our tasks on pretrained LLMs of different sizes (Qwen2.5-7B-Instruct, Mistral-Small-24B-Instruct-2501, Llama-3.3-70B-Instruct). Taken together, our results may help explain why existing methods for CoT reasoning with Transformers have empirically exhibited limitations with respect to length generalization. Turing completeness is not guaranteed, but rather depends heavily on the specific formatting of the CoT. By taking the learnability of the CoT format into account, we can create more effective schemes that may actually realize this underlying computational power. Figure 1: Barriers to universal CoT and overcoming them: (A.1) Simulating TM computations requires arbitrary addressing and retrieval of previously written tape positions. Simulating this does not length-generalize; we address it by assigning unique signpost tokens addressing the cells. (A.2) Even with signposts, recovering the latest content of a cell from the CoT trace becomes a non-unique retrieval problem ( 29 ) , for which also there is no length generalizable solution. Hence, we use a value change encoding to explicitly record changes rather than just values (i.e., record the new value relative to the old value), but only when there is a change. This allows computing the current value by comparing the counts of changes between each symbol pair (Section 3.3 ). These theoretical ideas have implications for formatting inputs and CoTs alike. (B.1) Putting signposts tokens according to the post-order traversal order of a Boolean formula in the input can help enable a transformer solve this hard task (Section 4.1 ). (B.2) Ascertaining the final value of a variable after multiple intermediate assignments when the changes of values are recorded in comments can make LLMs output the correct answer (Section 4.2 ). 2 Background 2.1 Related Work Empirical failures seen for CoT & steps to improve them. A substantial literature shows that CoT does not, by itself, guarantee length generalization. Across algorithmic ( 3 ; 14 ) , logical ( 23 ; 44 ; 45 ; 46 ) , planning ( 49 ) , and symbolic reasoning tasks ( 37 ; 7 ) , prior work finds that performance often degrades sharply with increasing problem length or number of reasoning steps, even when intermediate reasoning traces are provided or elicited, suggesting that the benefits of CoT are fragile in out-of-distribution settings. At the same time, several works show that the form of CoT can matter substantially. Adding padding ( 20 ) , modified scratchpad formats ( 1 ) , and more structured intermediate representations or specific positional encodings (PEs) ( 48 ; 31 ; 19 ) have been shown to improve length generalization across tasks, and even on harder tasks such as parity ( 24 ) which are hard to do without CoT ( 11 ) . However, these gains are highly sensitive to the chosen representation and do not imply that arbitrary