# Atom of Thoughts for Markov LLM Test-Time Scaling

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

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 47 of its 74 references that are in the map.
- First posted on arXiv 17 Feb 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

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

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [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)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework](https://mlsanity.com/paper/2308.00352/) (2023)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps](https://mlsanity.com/paper/2011.01060/) (2020)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [MuSiQue: Multihop Questions via Single-hop Question Composition](https://mlsanity.com/paper/2108.00573/) (2021)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Automatic Chain of Thought Prompting in Large Language Models](https://mlsanity.com/paper/2210.03493/) (2022)
- [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023)
- [LLM-Blender: Ensembling Large Language Models with Pairwise Ranking and Generative Fusion](https://mlsanity.com/paper/2306.02561/) (2023)
- [Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models](https://mlsanity.com/paper/2305.04091/) (2023)
- [LIMO: Less is More for Reasoning](https://mlsanity.com/paper/2502.03387/) (2025)
- [AFlow: Automating Agentic Workflow Generation](https://mlsanity.com/paper/2410.10762/) (2024)
- [Demystifying Long Chain-of-Thought Reasoning in LLMs](https://mlsanity.com/paper/2502.03373/) (2025)
- [Data Interpreter: An LLM Agent For Data Science](https://mlsanity.com/paper/2402.18679/) (2024)

## Built on by (most cited first, 30 of 54)

- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [R1-Searcher: Incentivizing the Search Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2503.05592/) (2025)
- [From System 1 to System 2: A Survey of Reasoning Large Language Models](https://mlsanity.com/paper/2502.17419/) (2025)
- [A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?](https://mlsanity.com/paper/2503.24235/) (2025)
- [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)
- [A Survey of LLM-based Deep Search Agents: Paradigm, Optimization, Evaluation, and Challenges](https://mlsanity.com/paper/2508.05668/) (2025)
- [Learning Adaptive Parallel Reasoning with Language Models](https://mlsanity.com/paper/2504.15466/) (2025)
- [SimpleDeepSearcher: Deep Information Seeking via Web-Powered Reasoning Trajectory Synthesis](https://mlsanity.com/paper/2505.16834/) (2025)
- [R1-Searcher++: Incentivizing the Dynamic Knowledge Acquisition of LLMs via Reinforcement Learning](https://mlsanity.com/paper/2505.17005/) (2025)
- [A Survey of Data Agents: Emerging Paradigm or Overstated Hype?](https://mlsanity.com/paper/2510.23587/) (2025)
- [System-1.5 Reasoning: Traversal in Language and Latent Spaces with Dynamic Shortcuts](https://mlsanity.com/paper/2505.18962/) (2025)
- [SCRIBE: Structured Mid-Level Supervision for Tool-Using Language Models](https://mlsanity.com/paper/2601.03555/) (2026)
- [Learning Global Hypothesis Space for Enhancing Synergistic Reasoning Chain](https://mlsanity.com/paper/2602.09794/) (2026)
- [Concise Reasoning, Big Gains: Pruning Long Reasoning Trace with Difficulty-Aware Prompting](https://mlsanity.com/paper/2505.19716/) (2025)
- [EllieSQL: Cost-Efficient Text-to-SQL with Complexity-Aware Routing](https://mlsanity.com/paper/2503.22402/) (2025)
- [Atomic-to-Compositional Generalization for Mobile Agents with A New Benchmark and Scheduling System](https://mlsanity.com/paper/2506.08972/) (2025)
- [InteractComp: Evaluating Search Agents With Ambiguous Queries](https://mlsanity.com/paper/2510.24668/) (2025)
- [Taming Text-to-Sounding Video Generation via Advanced Modality Condition and Interaction](https://mlsanity.com/paper/2510.03117/) (2025)
- [A Survey on Parallel Reasoning](https://mlsanity.com/paper/2510.12164/) (2025)
- [SPRINT: Enabling Interleaved Planning and Parallelized Execution in Reasoning Models](https://mlsanity.com/paper/2506.05745/) (2025)
- [ETVA: Evaluation of Text-to-Video Alignment via Fine-grained Question Generation and Answering](https://mlsanity.com/paper/2503.16867/) (2025)
- [Revisiting Test-Time Scaling: A Survey and a Diversity-Aware Method for Efficient Reasoning](https://mlsanity.com/paper/2506.04611/) (2025)
- [Test-time Scaling Techniques in Theoretical Physics -- A Comparison of Methods on the TPBench Dataset](https://mlsanity.com/paper/2506.20729/) (2025)
- [DeepVIS: Bridging Natural Language and Data Visualization Through Step-wise Reasoning](https://mlsanity.com/paper/2508.01700/) (2025)
- [Will Pre-Training Ever End? A First Step Toward Next-Generation Foundation MLLMs via Self-Improving Systematic Cognition](https://mlsanity.com/paper/2503.12303/) (2025)
- [SSR: Socratic Self-Refine for Large Language Model Reasoning](https://mlsanity.com/paper/2511.10621/) (2025)
- [Atomic Thinking of LLMs: Decoupling and Exploring Mathematical Reasoning Abilities](https://mlsanity.com/paper/2509.25725/) (2025)
- [MathMist: A Parallel Multilingual Benchmark Dataset for Mathematical Problem Solving and Reasoning](https://mlsanity.com/paper/2510.14305/) (2025)
- [Multilingual Test-Time Scaling via Initial Thought Transfer](https://mlsanity.com/paper/2505.15508/) (2025)

## Abstract (arXiv)

Large Language Models (LLMs) have achieved significant performance gains through test-time scaling methods. However, existing approaches often incur redundant computations due to the accumulation of historical dependency information during inference. To address this challenge, we leverage the memoryless property of Markov processes to minimize reliance on historical context and propose a Markovian reasoning process. This foundational Markov chain structure enables seamless integration with various test-time scaling methods, thereby improving their scaling efficiency. By further scaling up the Markovian reasoning chain through integration with techniques such as tree search and reflective refinement, we uncover an emergent atomic reasoning structure, where reasoning trajectories are decomposed into a series of self-contained, low-complexity atomic units. We name this design Atom of Thoughts (our). Extensive experiments demonstrate that our consistently outperforms existing baselines as computational budgets increase. Importantly, our integrates seamlessly with existing reasoning frameworks and different LLMs (both reasoning and non-reasoning), facilitating scalable, high-performance inference.We submit our code alongside this paper and will make it publicly available to facilitate reproducibility and future research.