Atom of Thoughts for Markov LLM Test-Time Scaling

However, as the scale of reasoning increases, existing test-time scaling methods suffer from accumulated historical information, which not only wastes computational resources but also interferes with effective reasoning. To address this issue, we observe that complex reasoning can be achieved by solving a series of independent and self-contained subquestions. These subquestions are essentially atomic questions, exhibiting the memoryless property similar to Markov processes. Based on this observation, we propose Atom of Thoughts (AOT), where each state transition consists of decomposing the current question into a dependency-based directed acyclic graph and contracting its subquestions, forming a simplified question that maintains answer equivalence with the original problem. This answer preservation enables the iterative decomposition-contraction process to naturally form a meaningful Markov reasoning process. Furthermore, these atomic states can be seamlessly integrated into existing testtime scaling methods, enabling AOT to serve as a plug-in enhancement for improving reasoning capabilities.

However, existing test-time scaling methods excessively maintain historical information during reasoning, as they rely heavily on complex structural dependencies throughout the reasoning process. Chain-based methods must preserve the entire reasoning history to generate each subsequent step (Wei et al., 2022; Zhang et al., 2023), while tree-based approaches require tracking both ancestor and sibling relationships for branch selection (Yao et al., 2023; Zhou et al., 2024a; Ding et al., 2024). Graph-based structures further compound these challenges through arbitrary node dependencies (Besta et al., 2024; Zhang et al., 2024c). As the scale of reasoning increases, the accumulation of historical dependencies not only wastes substantial computational resources but also interferes with the model’s ability to reason effectively, as illustrated in Figure 1.

Inspired by this Markov nature of human reasoning, we propose Atom of Thoughts (AOT), a framework that realizes the Markov-style reasoning process. Our key insight is that each reasoning state can be defined as a simplified problem equivalent to the original one, where partial reasoning steps are either transformed into known conditions or excluded as incorrect explorations

Human reasoning often progresses through solving a sequence of independent subquestions, a fundamental principle established in cognitive science (Simon, 1962) and problem-solving theory (Polya, 1945). When solving a complex problem, we naturally identify and resolve self-evident subquestions first, then seamlessly incorporate these solutions to reformulate a simplified problem state, rather than maintaining detailed reasoning processes for resolved components. This progression closely resembles a Markov process (Markov, 1906), where each state represents a question, and state transitions occur through resolving partial problems to form new, independent questions.

 Inspired by this Markov nature of human reasoning, we propose Atom of Thoughts (AOT), a framework that realizes the Markov-style reasoning process. Our key insight is that each reasoning state can be defined as a simplified problem equivalent to the original one, where partial reasoning steps are either transformed into known conditions or excluded as incorrect explorations. This definition is achieved through a two-phase state transition mechanism: first decomposing the current question into a dependency-based directed acyclic graph (DAG) to capture rich structural information, then contracting subquestions into a new independent question. This iterative decomposition-contraction process continues until reaching directly solvable atomic questions, ensuring each state transition depends only on the current state while progressively reducing problem complexity.

 This design endows AOT with two key advantages. First, AOT eliminates the need for maintaining and computing historical information when scaling computational resources. Second, these atomic questions can be seamlessly integrated into existing test-time scaling frameworks, allowing AOT to function as either a standalone framework or a plug-in enhancement for improving the overall reasoning capabilities. In summary, our contributions