# Markov Chain of Thought for Efficient Mathematical Reasoning

arXiv: https://arxiv.org/abs/2410.17635 · HTML: https://mlsanity.com/paper/2410.17635/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning.
- Builds on 35 of its 56 references that are in the map.
- First posted on arXiv 23 Oct 2024.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

## Builds on (most cited first, 30 of 35)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Retrieval-Augmented Generation for Large Language Models: A Survey](https://mlsanity.com/paper/2312.10997/) (2023)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [LlamaFactory: Unified Efficient Fine-Tuning of 100+ Language Models](https://mlsanity.com/paper/2403.13372/) (2024)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [PaLM 2 Technical Report](https://mlsanity.com/paper/2305.10403/) (2023)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [MetaMath: Bootstrap Your Own Mathematical Questions for Large Language Models](https://mlsanity.com/paper/2309.12284/) (2023)
- [WizardMath: Empowering Mathematical Reasoning for Large Language Models via Reinforced Evol-Instruct](https://mlsanity.com/paper/2308.09583/) (2023)
- [Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models](https://mlsanity.com/paper/2305.04091/) (2023)
- [MAmmoTH: Building Math Generalist Models through Hybrid Instruction Tuning](https://mlsanity.com/paper/2309.05653/) (2023)
- [Llemma: An Open Language Model For Mathematics](https://mlsanity.com/paper/2310.10631/) (2023)
- [FUDGE: Controlled Text Generation With Future Discriminators](https://mlsanity.com/paper/2104.05218/) (2021)
- [Effective Long-Context Scaling of Foundation Models](https://mlsanity.com/paper/2309.16039/) (2023)
- [ToRA: A Tool-Integrated Reasoning Agent for Mathematical Problem Solving](https://mlsanity.com/paper/2309.17452/) (2023)
- [LongLoRA: Efficient Fine-tuning of Long-Context Large Language Models](https://mlsanity.com/paper/2309.12307/) (2023)
- [AlphaMath Almost Zero: Process Supervision without Process](https://mlsanity.com/paper/2405.03553/) (2024)
- [MathCoder: Seamless Code Integration in LLMs for Enhanced Mathematical Reasoning](https://mlsanity.com/paper/2310.03731/) (2023)
- [Same Task, More Tokens: the Impact of Input Length on the Reasoning Performance of Large Language Models](https://mlsanity.com/paper/2402.14848/) (2024)
- [Question Decomposition Improves the Faithfulness of Model-Generated Reasoning](https://mlsanity.com/paper/2307.11768/) (2023)
- [Successive Prompting for Decomposing Complex Questions](https://mlsanity.com/paper/2212.04092/) (2022)
- [MARIO: MAth Reasoning with code Interpreter Output -- A Reproducible Pipeline](https://mlsanity.com/paper/2401.08190/) (2024)
- [Iteratively Prompt Pre-trained Language Models for Chain of Thought](https://mlsanity.com/paper/2203.08383/) (2022)

## Built on by (most cited first, 19 of 19)

- [Advances and Challenges in Foundation Agents: From Brain-Inspired Intelligence to Evolutionary, Collaborative, and Safe Systems](https://mlsanity.com/paper/2504.01990/) (2025)
- [Efficient Reasoning Models: A Survey](https://mlsanity.com/paper/2504.10903/) (2025)
- [Atom of Thoughts for Markov LLM Test-Time Scaling](https://mlsanity.com/paper/2502.12018/) (2025)
- [StreamAgent: Towards Anticipatory Agents for Streaming Video Understanding](https://mlsanity.com/paper/2508.01875/) (2025)
- [Can Pruning Improve Reasoning? Revisiting Long-CoT Compression with Capability in Mind for Better Reasoning](https://mlsanity.com/paper/2505.14582/) (2025)
- [Causal Sufficiency and Necessity Improves Chain-of-Thought Reasoning](https://mlsanity.com/paper/2506.09853/) (2025)
- [Generative AI Act II: Test Time Scaling Drives Cognition Engineering](https://mlsanity.com/paper/2504.13828/) (2025)
- [An Efficient and Precise Training Data Construction Framework for Process-supervised Reward Model in Mathematical Reasoning](https://mlsanity.com/paper/2503.02382/) (2025)
- [ACE-RL: Adaptive Constraint-Enhanced Reward for Long-form Generation Reinforcement Learning](https://mlsanity.com/paper/2509.04903/) (2025)
- [Old Habits Die Hard: How Conversational History Geometrically Traps LLMs](https://mlsanity.com/paper/2603.03308/) (2026)
- [Markovian Scale Prediction: A New Era of Visual Autoregressive Generation](https://mlsanity.com/paper/2511.23334/) (2025)
- [When does Chain-of-Thought Help: A Markovian Perspective](https://mlsanity.com/paper/2603.00306/) (2026)
- [Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack Efficiently](https://mlsanity.com/paper/2606.22938/) (2026)
- [Can I Have Your Order? Monte-Carlo Tree Search for Slot Filling Ordering in Diffusion Language Models](https://mlsanity.com/paper/2602.12586/) (2026)
- [OVOD-Agent: A Markov-Bandit Framework for Proactive Visual Reasoning and Self-Evolving Detection](https://mlsanity.com/paper/2511.21064/) (2025)
- [Ladder Up, Memory Down: Low-Cost Fine-Tuning With Side Nets](https://mlsanity.com/paper/2512.14237/) (2025)
- [Answering the Wrong Question: Reasoning Trace Inversion for Abstention in LLMs](https://mlsanity.com/paper/2604.02230/) (2026)
- [ConCise: Training-Free Conclusion-Chain State Compression for Cost-Efficient Multi-Step RAG Services](https://mlsanity.com/paper/2606.28361/) (2026)
- [When Tokenization is Secretly Output Supervision](https://mlsanity.com/paper/2609.01386/) (2026)

## Abstract (arXiv)

Chain of Thought (CoT) of multi-step benefits from the logical structure of the reasoning steps and task-specific actions, significantly enhancing the mathematical reasoning capabilities of large language models. As the prevalence of long CoT, the number of reasoning steps exceeds manageable token limits and leads to higher computational demands. Inspired by the fundamental logic of human cognition, "derive, then reduce", we conceptualize the standard multi-step CoT as a novel Markov Chain of Thought (MCoT). In this study, we consider the mathematical reasoning task, defining each reasoning step as text accompanied by a Python code snippet. To facilitate a longer reasoning path, self-correction is enabled through interactions with the code interpreter. Our MCoT aims to compress previous reasoning steps into a simplified question, enabling efficient next-step inference without relying on a lengthy KV cache. In our experiments, we curate the textttMCoTInstruct dataset, and the empirical results indicate that MCoT not only significantly enhances efficiency but also maintains comparable accuracy. While much remains to be explored, this work paves the way for exploring the long CoT reasoning abilities of LLMs. The code is available at https://github.com/james-yw/Markov-Chain-of-Thought