The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought
For the transformer theory community, this bridges the gap between expressivity results and practical models by showing that realistic transformers (softmax, low precision) are computationally powerful.
The paper proves that standard softmax transformers with low precision and logarithmic depth/width can simulate Turing machines using Chain-of-Thought, and shows that summarized CoT is more efficient. Empirical results on Sudoku confirm better alignment with learnability than prior high-precision results.
Existing expressivity results for transformers typically rely on hardmax attention, high precision, and other architectural modifications that disconnect them from the models used in practice. We bridge this gap by analyzing standard transformer decoders with softmax attention and rounding of activations and attention weights, while allowing depth and width to grow logarithmically with the context length. As an intermediate step, we construct hardmax transformers with ternary activations and well-separated attention scores that simulate Turing machines using Chain-of-Thought (CoT). This lets us convert the constructions to equivalent softmax transformers without the unrealistic parameter magnitudes or activation precision that prior approaches would require. Using the same technique, we analyze a recently proposed summarized CoT paradigm and show that it simulates Turing machines more efficiently, with model size scaling logarithmically in a space bound rather than a time bound. We empirically test predictions made by our results on a Sudoku reasoning task and find better alignment with learnability than for prior high-precision results. Our code is available at https://github.com/moritzbroe/transformer-expressivity.