A Formal Comparison Between Chain of Thought and Latent Thought

arxiv:2509.25239

Original source · Paper JSON

Reasoning and the "physics" of language models · 2025-09-25

Cites (4) · Cited by (3)

Complete cleaned Markdown · Source Markdown including bibliography

Read in parts

1. Part 1
2. Part 2
3. Part 3
4. Part 4
5. Part 5
6. Part 6
7. Part 7
8. Part 8
9. Part 9

Contents

• A Formal Comparison Between Chain of Thought and Latent Thought
• Abstract
• Keywords:
• 1 Introduction
• 1.1 Our Contributions
• Latent thought enables parallel reasoning.
• CoT enables approximate counting.
• 2 Background
• 2.1 Models of Computation
• Definition 2.1 (CoT, following Merrill and Sabharwal (2024) ) .
• Definition 2.2 (Coconut) .
• Definition 2.3 (Looped TF) .
• 2.2 Related Work
• Computational power of chain of thought.
• Computational power of latent thought.
• 3 Latent Thought Enables Parallel Reasoning
• 3.1 Problem Setting
• Definition 3.1 (Computation graph) .
• Assumptions on models.
• On the fairness of comparing steps and loops.
• 3.2 CoT Suffices with Size-scaled Steps and Latent Thought Suffices with Depth-scaled Iterations
• Definition 3.2 ( Merrill and Sabharwal, 2023 ) .
• Assumption 3.3 (Poly-size graph) .
• Assumption 3.4 (Poly-efficient approximation, cf. ( Feng et al., 2023 ) ) .
• Theorem 3.5 (CoT for DAGs) .
• Proof sketch.
• Theorem 3.6 (Latent thought for DAGs) .
• Proof sketch.
• Remark.
• 3.3 Separation in Polylogarithmic Iterations
• Definition 3.7 (Complexity Classes 𝖢𝗈𝖳 \mathsf{CoT} , 𝖢𝖳 \mathsf{CT} and 𝖫𝗈𝗈𝗉 \mathsf{Loop} ) .
• Definition 3.8 (Informal) .
• Theorem 3.9 ( Li et al., 2024 ) .
• Theorem 3.10 .
• Definition 3.11 .
• Theorem 3.12 .
• Proof sketch.
• Lemma 3.13 .
• Proof.
• Theorem 3.14 .
• Theorem 3.15 .
• Remark.
• 4 CoT Enables Approximate Counting
• 4.1 Preliminaries
• Approximate counting.
• Definition 4.1 (Informal: Self-reducibility ( Schnorr, 1976 ) ) .
• Definition 4.2 (FPRAS) .
• Probabilistic models of computation.
• 4.2 Separation in Approximate Counting
• Lemma 4.3 (Informal) .
• Proof sketch.
• 4.3 Separation in Approximate Sampling
• Theorem 4.4 .
• Proof sketch.
• Theorem 4.5 .
• 5 Experiments
• 5.1 Experimental Setting
• Fundamental algorithmic reasoning tasks.
• Approximate counting tasks.
• Training strategy.
• 5.2 Results
• 6 Conclusion
• Impact Statement
• Appendix A Formal Definitions
• A.1 Notation
• A.2 Transformer Block
• Definition A.1 (Transformer) .
• A.3 Chain of Thought
• Definition A.2 (CoT) .
• A.4 Continuous Thought
• Definition A.3 (Coconut) .
• A.5 Looped Transformer
• Definition A.4 (Looped TF) .
• Appendix B Deferred Proofs for Section 3
• B.1 Precision Modeling
• Definition B.1 (Floating-point Representation, cf. ( Li et al., 2024 ) ) .
• Definition B.2 (Correct Rounding, cf. ( Li et al., 2024 ) ) .
• Definition B.3 (Summation with Iterative Rounding ( Li et al., 2024 ) ) .
• B.2 Definition of Assumption 3.4
• Definition B.4 (Polynomially-efficient approximation) .
• B.3 Technical lemmas
• B.3.1 Orthogonal Vectors
• Lemma B.5 ( Li et al., 2024 ) .
• B.3.2 Position Selector
• Lemma B.6 .
• Proof.
• B.3.3 Feedforward layers
• Lemma B.7 .
• Proof.
• Lemma B.8 .
• Proof.
• B.4 Proof for Theorem 3.5
• Proof.
• Embedding
• Attention layer
• Feed-forward layer
• Output layer
• B.5 Proof of Theorem 3.6 for Looped Transformer
• Proof.
• Summary
• B.6 Proof of Theorem 3.6 for Continuous Thought
• Proof.
• B.7 Proof for Theorem 3.12
• Theorem B.9 ( Li et al., 2024 ) .
• Lemma B.10 ( Li et al., 2024 ) .
• Proof for Theorem 3.12 .
• Appendix C Deferred Proofs for Section 4
• C.1 Definition for Models of Computation
• Definition C.1 (Language model with CoT) .
• Definition C.2 (Language model with Coconut) .
• Definition C.3 (Language model with looped TF) .
• Definition C.4 (Complexity Classes 𝗉𝖢𝗈𝖳 \mathsf{pCoT} , 𝗉𝖢𝖳 \mathsf{pCT} , and 𝗉𝖫𝖮𝖮𝖯 \mathsf{pLOOP} ) .
• C.2 Lemma: Universality of Chain of Thought
• Definition C.5 .
• Lemma C.6 ( Nowak et al., 2024 ) .
• C.3 Self-Reducibility and Complexity of Approximate Counting
• Definition C.7 (Relation) .
• Definition C.8 (Counting) .
• Definition C.9 ( p p -relation) .
• Definition C.10 .
• Definition C.11 (FPTAS) .
• Definition C.12 (FPRAS) .
• Proposition C.13 ( Jerrum et al., 1986 ) .
• Proposition C.14 .
• Proof.
• Proof for Proposition C.13 .
• Definition C.15 ( Schnorr, 1976 ) .
• Proposition C.16 ( Jerrum et al., 1986 ) .
• Proof.
• C.4 Proof for Theorem 4.3
• Lemma C.17 (Formal Statement of Lemma 4.3 ) .
• Proof.
• C.5 Proof for Theorem 4.4
• Definition C.18 (FPAUS) .
• Theorem C.19 ( Jerrum et al., 1986 ) .
• Proof of Theorem 4.4 .
• Appendix D Experimental Details
• D.1 Fundamental Algorithmic Reasoning Tasks
• D.1.1 Task Settings
• Word Problem
• Connectivity
• Arithmetic Expression Evaluation
• Edit Distance
• D.1.2 Training Configuration
• Configuration of chain of thought
• Optimization and model details.
• Uniform selection.
• Stepwise internalization.
• D.2 Approximate Counting and Approximate Sampling
• D.2.1 Approximate Counting of DNF Formulas
• D.2.2 Approximate Sampling of Graph Colorings
• Instructions for reporting errors