Barriers to Universal Reasoning With Transformers (And How to Overcome Them)

1. Problem Statement

While Chain-of-Thought (CoT) prompting has empirically improved the performance of Transformers and has been theoretically shown to increase their expressivity to Turing-completeness, a critical gap remains: Can Transformers learn to generalize CoT reasoning to lengths longer than those seen during training?

Existing empirical evidence suggests that the accuracy of Transformers declines sharply with increasing CoT trace length, even on algorithmic and logical tasks. The paper investigates whether the theoretical claim of Turing-completeness holds under the stricter requirement of length-generalizable learnability. Specifically, it asks:

• Do standard CoT formats allow Transformers to solve problems outside the complexity class $\text{TC}^0$ (constant-depth threshold circuits) when generalized to longer sequences?
• What specific structural barriers prevent this generalization?
• Can these barriers be overcome through specific formatting strategies?

2. Methodology

The authors employ a combination of theoretical formalism and empirical validation:

Theoretical Framework

The study utilizes recent theoretical frameworks for length generalization in Transformers:

• C-RASP: A formalism for reasoning about Transformers with finite alphabets and positional encodings. Membership implies guarantees for length generalization.
• C-RASP:* An extension of C-RASP that allows an infinite alphabet (specifically unbounded pointer tokens) and local match predicates.
• Learning Model: The authors adopt an idealized learning model where a sequence of Transformers trained on increasing input lengths converges toward a single underlying algorithm. Generalization is guaranteed if the task is expressible within these formalisms.

Empirical Setup

• Tasks: Three algorithmic reasoning tasks were selected:
  1. Parity: Determining whether the number of 1s in a binary string is even or odd.
  2. Boolean Evaluation: Evaluating the truth value of nested logical formulas.
  3. S5 Permutation: Tracking the state of 5 objects after a series of swap operations.
• Models:
  • From-Scratch: GPT-2 models (25 million parameters), trained on CoT traces with and without specific formatting.
  • Pre-trained LLMs: Zero-shot and few-shot prompting experiments with Qwen2.5-7B, Mistral-Small-24B, and Llama-3.3-70B.
• Formatting Variants:
  • Naive CoT: Standard sequential reasoning.
  • Pointer Tokens: Assigning unique identifiers (e.g., <34>) to specific positions or operations to enable arbitrary addressing.
  • Value-Change Encoding: Instead of logging the entire state at each step, the model logs only changes to values (e.g., 1 -> 0) or explicitly notes when a value remains unchanged.

3. Main Contributions and Theoretical Results

Contribution 1: The Limit of Finite Alphabets (The Negative Result)

The authors prove that Transformers with CoT under standard positional encodings and a finite alphabet cannot generalize to solving problems outside of $\text{TC}^0$.

• Theorem 3.4: If a language $L$ possesses a CoT trace expressible in C-RASP (with position primitives), then $L$ is definable in $\text{TC}^0$.
• Implication: Although CoT theoretically enables Turing-completeness, the learnability of such simulations is bounded by $\text{TC}^0$ when the vocabulary is fixed. The benefits of expressivity do not translate to length-generalizable learnability.

Contribution 2: Overcoming Barriers with Infinite Alphabets (The Positive Result)

The paper identifies two core barriers to length generalization:

1. Repeated Copying: The difficulty of copying arbitrary strings to new positions.
2. Retrieving the Last Occurrence: The difficulty of retrieving the most current value of a variable when multiple updates occur (non-unique retrieval).

To overcome these, the authors propose a construction using C-RASP*:

• Pointer Tokens: Assigning a unique, unbounded token (from an infinite alphabet) to each tape position or operation step. This resolves the copying barrier by enabling arbitrary indexing without needing to memorize absolute identities.
• Value-Change Encoding: Instead of logging the entire state, the CoT logs only transitions (e.g., "value changed from $x$ to $y$"). The current state is recovered by counting net changes relative to the initial state. This resolves the retrieval barrier by making the current value a function of counts rather than searching for the "last" occurrence.
• Theorem 3.8: Transformers with CoT can behave length-generally to simulate any Turing machine if they utilize an infinite alphabet of pointer tokens and encode computations over value changes. The length of the CoT trace remains linear in the simulated runtime behavior.

4. Empirical Results

Training From-Scratch

• Parity: Standard CoT failed to generalize beyond training lengths. Value-change encoding enabled robust generalization to $2\times$ the training length.
• Boolean Evaluation & S5 Permutation: These harder tasks (outside $\text{TC}^0$) failed with naive CoT. Adding pointer tokens significantly improved length generalization, although S5 remained challenging due to potential "shortcuts" (heuristics) the model might exploit.
• Binary Permutation: A variant of S5 with high repetition. Naive and pointer-only CoTs failed due to "non-unique retrieval" errors. The combination of pointers + value change achieved the best results, confirming the theoretical necessity of both mechanisms.

Prompting Pre-trained LLMs

• Pointers: Using natural numbers as pointer hints in few-shot prompts improved performance on Boolean and S5 tasks for all tested LLMs (7B to 70B), particularly on longer sequence lengths.
• Value Change: In a code execution task (tracking variable assignments), providing inline comments that explicitly logged value changes (e.g., # node a: 9 -> 0) significantly improved the accuracy of the final answer compared to standard code formatting, even without intermediate reasoning steps.

5. Significance and Conclusion

• Redefining CoT Success: The paper argues that CoT success is not inherently due to the "thinking" process itself but depends heavily on the formatting of the trace. Standard CoT formats often fail to generalize because they violate locality and translation invariance constraints required for learnability.
• Theoretical Limits: It clarifies that Turing-completeness for Transformers is conditional. It holds for expressivity (hard-coding a solution) but not for learnability (training a model to generalize) unless specific structural aids (infinite alphabets/pointers) are provided.
• Practical Guidelines: The findings offer actionable principles for improving LLM performance on difficult reasoning tasks:
  1. Use Index Hints: Explicitly mark positions or steps with unique identifiers to support retrieval.
  2. Log Changes, Not States: Format reasoning traces to highlight state transitions rather than full state extractions to avoid retrieval ambiguities.
• Future Directions: The work suggests that future pre-training data and CoT schemes should be developed considering these theoretical constraints to unlock the full computational potential of Transformers on long-horizon tasks.

In summary, the paper demonstrates that while Transformers are theoretically capable of universal reasoning, realizing this capability in a length-generalizable manner requires overcoming specific architectural and formatting barriers through the use of pointer tokens and value-change encodings.