Research map / Large language models / Reasoning and chain of thought

Efficiently Representing Algorithms With Chain-of-Thought Transformers

NeurIPS 2026 · Large language models › Reasoning and chain of thought · approach: Chain-of-thought training and analysis · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that chain-of-thought transformers can simulate Word RAM algorithms with only polylogarithmic overhead per instruction, via three constructions: polylog-width UHAT, fixed-width continuous CoT, and fixed-width hybrid transformer-linear RNN models.

Problem

Existing chain-of-thought expressivity results simulate Turing machines, incurring quadratic overhead relative to Word RAM algorithms; it is unclear whether CoT transformers can efficiently simulate textbook algorithms at their Word RAM complexity.

Approach

Direct Word RAM instruction-level simulation: memory writes are logged to the CoT as memory blocks read back via rightmost-match attention in the polylog-width setting; fixed-width settings use layer-norm hash representations with continuous CoT soft tokens or a linear RNN layer to serialize and deserialize binary words.

Key results

• Polylog-width rightmost UHAT simulates flat Word RAM with O(t log^2 t) CoT steps for full-arithmetic and O(t log t) for simple-arithmetic instructions.
• Fixed-width log-precision continuous CoT transformers simulate Word RAM with O(t * T(w)) decoding steps, giving O(t log^2 t) or O(t log t) overhead under the same instruction classes.
• Hybrid transformer plus single linear RNN layer achieves the same O(t T(w)) simulation with explicit CoT.

Surprising findings

• Turing-machine-based CoT simulations incur quadratic overhead over Word RAM, which this work removes.

Limitations

• Polylog-width construction is non-uniform, requiring new parameters for longer inputs.
• Polylog-width construction requires rightmost unique hard attention.
• Unclear whether fixed-width plain transformers can simulate Word RAM efficiently.

Experimental setup

Metrics: asymptotic CoT step overhead

Baselines: Turing machine CoT simulations

Builds on: chain-of-thought Turing completeness rightmost unique hard attention transformers layer-norm hash representation Word RAM model

Closest papers by meaning

• Analyzing the Power of Chain of Thought through Memorization Capabilities (NeurIPS 2025 · similarity 0.91)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (ICLR 2024 · similarity 0.91)
• Continuous Chain of Thought Enables Parallel Exploration and Reasoning (ICLR 2026 · similarity 0.88)
• PENCIL: Long Thoughts with Short Memory (ICML 2025 · similarity 0.87)
• CoTFormer: A Chain of Thought Driven Architecture with Budget-Adaptive Computation Cost at Inference (ICLR 2025 · similarity 0.87)
• The Expressive Power of Transformers with Chain of Thought (ICLR 2024 · similarity 0.87)