Research map / Large language models / Reasoning and chain of thought
Analyzing the Power of Chain of Thought through Memorization Capabilities
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 via memorization theory that fixed-precision transformers with or without chain-of-thought need Θ̄(N) parameters on finite reasoning datasets, so CoT does not expand memorization power across all reasoning tasks.
Problem
Whether chain-of-thought expands the expressive capability of transformers across all reasoning tasks, cast as the memorization capacity of fixed-precision autoregressive transformers with and without CoT.
Approach
Reframes reasoning as memorizing a reasoning dataset and gives necessary and sufficient conditions for fixed-precision no-CoT and CoT transformers to memorize finite languages, plus matching Θ̄(N) parameter bounds; shows the two conditions are incomparable and that infinite languages like length counting and Arith_p cannot be memorized.
Key results
- Necessary and sufficient conditions for finite-language memorization by no-CoT and CoT transformers are given, and they are shown to be mutually non-implying.
- Both no-CoT and CoT transformers need Θ̄(N) parameters to memorize some finite languages of size N (matching upper and lower bounds).
- Length-counting infinite language LCP and Arith_p cannot be memorized by fixed-precision (or even unbounded-precision for LCP) transformers under the positive-confidence assumption.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CoT instead of direct prediction | Fixed-precision transformers on finite reasoning languages · Finite reasoning languages | memorization capability | Mixed |
| Use CoT instead of direct prediction | Transformers on LCP_n · LCP_n | memorization capability | No clear effect |
| Use CoT instead of direct prediction | Transformers on LCP_n^{=1} · LCP_n^{=1} | memorization capability | Helped |
| Use CoT instead of direct prediction | Transformers on LCP_n^{>1} · LCP_n^{>1} | memorization capability | Hurt |
| Add position encoding for the first L positions | No-CoT transformer on finite languages · Finite languages | memorization capability | Helped |
| Add position encoding | CoT transformer on languages whose inputs contain multiple distinct symbols · Finite languages not memorizable by CoT | memorization capability | No clear effect |
| Add basic symbols that do not appear in input sentences | CoT transformer · Finite languages whose input symbols are a proper subset of the available symbols | memorization capability | Helped |
| Use CoT instead of direct prediction | Transformers on an infinite sub-language of LCP · Infinite sub-language of LCP | memorization capability | No clear effect |
| Use CoT instead of direct prediction | Transformers on arithmetic in Z_p with positive confidence · Arithmetic in Z_p | solving with confidence | No clear effect |
| Use CoT instead of direct prediction | Transformers memorizing finite languages · Finite languages with N elements | necessary parameter count: O(\frac{N\ln T}{q}) | No clear effect |
Surprising findings
- Position encoding helps no-CoT transformers memorize more languages but does not help CoT transformers.
- Adding extra basic symbols helps CoT transformers memorize all finite languages but has no effect for no-CoT transformers.
Limitations
- Only single-token labels are considered.
- LayerNorm is ignored and most results omit positional encoding.
- Arith_p impossibility is proved only under a positive-confidence assumption and the fixed-precision case is left as a conjecture.
Experimental setup
Datasets: Arith_p (arithmetic in Z_p, synthetic definition) length calculation problem LCP (synthetic definition)
Builds on: chain-of-thought prompting memorization capacity of transformers
Closest papers by meaning
- Efficiently Representing Algorithms With Chain-of-Thought Transformers (NeurIPS 2026 · similarity 0.91)
- Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (ICLR 2024 · similarity 0.90)
- PENCIL: Long Thoughts with Short Memory (ICML 2025 · similarity 0.89)
- How Does Chain of Thought Think? Mechanistic Interpretability of Chain-of-Thought Reasoning with Sparse Autoencoding (AAAI 2026 · similarity 0.88)
- A Formal Comparison Between Chain of Thought and Latent Thought (ICML 2026 · similarity 0.88)
- From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.