Efficiently Representing Algorithms With Chain-of-Thought Transformers

The recent preprint from arXiv (2606.19697) tackles a foundational question in the mechanics of large language models: how efficiently can a transformer represent an algorithm when forced to use chain-of-thought (CoT) reasoning? The paper provides formal theoretical bounds, demonstrating that CoT transformers can represent algorithms with significantly fewer layers than standard transformers, effectively trading depth for sequential thought tokens.

What Happened

The researchers analyzed the computational capacity of transformers that output intermediate "thought" tokens before a final answer — the core mechanism behind modern reasoning models like OpenAI’s o1 and DeepSeek-R1. They prove that a CoT transformer with a constant number of layers can simulate any algorithm that runs in polynomial time, provided the chain-of-thought length is allowed to grow polynomially. Conversely, they show that without CoT, a transformer would need a number of layers proportional to the algorithm’s depth, which can be exponentially larger for certain problems.

This is not an empirical benchmark paper; it is a theoretical characterization. It formalizes what practitioners have observed empirically: that CoT allows models to "think" step-by-step, effectively using the token sequence as a computational scratchpad.

Why It Matters

This result provides a rigorous justification for the industry-wide pivot toward reasoning models. The key insight is that CoT transforms a transformer from a fixed-depth circuit into a programmable machine. In standard transformers, the number of layers caps the logical depth of computations the model can perform. CoT removes that bottleneck by allowing the model to "write" intermediate results into the output sequence, which can then be read back in subsequent tokens.

For AI practitioners, this has direct architectural implications. It suggests that investing in longer CoT sequences (e.g., via reinforcement learning to encourage thorough reasoning) is a more scalable path to solving complex problems than simply stacking more transformer layers. The paper implies that a 32-layer model with 10,000 reasoning tokens can, in theory, solve problems that would require a 10,000-layer model without CoT.

Implications for AI Practitioners

First, optimize for CoT quality, not just model size. The theoretical results suggest that a smaller model with well-trained CoT reasoning can outperform a larger model that answers directly. This aligns with recent trends where models like Claude 3.5 Sonnet and GPT-4o-mini with CoT prompting match or exceed larger models on reasoning benchmarks.

Second, latency is the new compute budget. The paper’s trade-off is clear: CoT requires more tokens per query, increasing latency and cost. Practitioners must balance the depth of reasoning against user experience. For real-time applications, shorter CoT or direct answers may be preferable; for complex analysis, longer CoT is justified.

Third, training data design matters. Since CoT effectively turns the model into a program executor, the quality of intermediate reasoning steps in training data directly determines the model’s ability to simulate algorithms. This reinforces the importance of process-level supervision (e.g., step-by-step reward models) over outcome-only supervision.

Key Takeaways

• CoT transformers can simulate polynomial-time algorithms with constant depth, proving that reasoning tokens are a computationally efficient substitute for additional layers.
• The trade-off is between model depth and token length: longer CoT sequences enable solving harder problems without scaling the model architecture.
• Practitioners should prioritize CoT training and inference optimization over simply increasing model size, as the theoretical gains from CoT are substantial.
• Latency and cost remain the primary practical constraints; the choice of CoT length should be tuned per use case based on required reasoning complexity.