Source-linked AI summary
Atom of Thoughts for Markov LLM Test-Time Scaling
Fengwei Teng, Quan Shi, Zhaoyang Yu, Jiayi Zhang, Yuyu Luo, Chenglin Wu, Zhijiang Guo
TL;DR
Existing test-time scaling methods incur redundant computation by retaining extensive historical dependencies during inference. AOT introduces Markovian state transitions with decomposition and contraction, then combines them with scaling methods to produce atomic reasoning units. The paper reports scalable, high-performance inference and flexible integration across reasoning frameworks, while identifying inference-only implementation and error propagation as limitations.
Problem
Existing reasoning frameworks retain extensive historical dependencies, creating redundant computation and potential interference during test-time inference.
Method
AOT uses memoryless Markovian state transitions with DAG-based decomposition and contraction, integrating with tree search and reflective refinement to form atomic reasoning units.
Results
AOT provides scalable, high-performance inference, integrates flexibly with existing reasoning paradigms, and supports maths, code, and multi-hop question answering.
Takeaways & Limitations
AOT offers a modular reasoning framework that can operate independently or as a plug-in module for existing inference methods.
Takeaways & Limitations
AOT currently operates only at inference time, and strict memorylessness can propagate low-quality transitions when intermediate states diverge from the original task.
Abstract
from arXiv · showhide
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.
1 Introduction
Existing test-time scaling methods accumulate historical dependencies, while AOT replaces this with memoryless state transitions and integrates scalable reasoning structures to improve efficiency and performance.
- Motivation: Framework-based test-time scaling methods retain extensive historical information, increasing computational burden during inference.CoT preserves the full trajectory, tree methods maintain ancestor and sibling relations, and graph methods add arbitrary node dependencies.
- Markovian Reasoning Process: AOT uses a Markovian reasoning process in which each self-contained state reduces historical dependencies and progressively lowers test-time complexity.Its two-phase transition decomposes the current state into a DAG-based reasoning path, then contracts that structure to generate the next state.
- Scalable Reasoning Structure: AOT integrates with existing test-time scaling methods, enabling combinations that improve computational efficiency without maintaining extensive historical contexts.The framework is designed for code generation, mathematical reasoning, and multi-step reasoning tasks.
- Atomic Reasoning: Integrating tree search and reflective refinement reveals atomic reasoning, where complex trajectories become sequences of self-contained, low-complexity units.The paper reports improved reasoning performance and robustness from this atomicization.
2 Related Work
Prior reasoning frameworks expand LLM inference through chains, trees, graphs, reflection, and tools, but often accumulate historical dependencies. AOT instead uses temporary DAG-assisted Markovian state transitions to reduce dependency overhead and integrate with existing methods.
- Existing Reasoning Frameworks: Structured reasoning methods use chains, graphs, and trees alongside cognitive operations and tools to explore solution spaces during inference.These approaches include step-by-step decomposition, reflective reasoning, recursive problem-solving, and dynamic path selection.
- Historical Dependencies: Framework-based and training-based approaches often rely on expansive historical context, which can increase computational costs and interfere with inference.Related Markovian and atomic approaches have also faced task-specific design limitations that hinder generalizability and efficient parallelism.
- AOT Perspective: AOT models reasoning as Markovian state transitions assisted by a temporary DAG, eliminating redundant history tracking and focusing computation on current-state transformations.Its decomposition and contraction stages support atomic problem-solving while reducing dependency overhead.
- Integration: AOT integrates with existing reasoning frameworks to support scalable, high-performance inference.The approach is presented as a structured yet flexible alternative to history-dependent methods.
3 Atomic Reasoning via Markov Process
The paper formulates reasoning as a memoryless Markov process whose states preserve answer-equivalence while reducing historical dependencies. A two-phase transition and quality-aware termination support stable inference, while integration with search and reflection reveals emergent atomic reasoning structures.
- Motivation: CoT and graph-based reasoning accumulate historical thoughts and dependencies, increasing the information that must be retained during inference.CoT preserves entire trajectories, while tree and graph methods maintain ancestor, sibling, or arbitrary node relations.
- Markovian Reasoning Process: The Markovian formulation represents reasoning as states where each subsequent state depends only on the current state and remains answer-equivalent to the original question.The original question initializes the process, and intermediate subquestions are reused as practical Markov states.
- Two-phase Transition: Each transition decomposes the current question into a temporary DAG and contracts its dependencies into the next self-contained state.Independent nodes are discarded, while dependent nodes are reformulated into an answer-equivalent independent question.
- Termination Strategy: A quality-aware termination strategy has an LLM judge select among solutions from the current state, its DAG, and the next state to retain semantically stable transformations.The selection mechanism filters transitions that fail to preserve answer-equivalence with the original question.
- Modular Integration: The Markov structure supports modular routing to specialized solvers, verification, tree search, and graph-based inference without maintaining extensive historical contexts.Its self-contained problem representations provide a structural foundation for combining diverse test-time reasoning strategies.
- Emerged Atomic Reasoning: Scaling Markovian trajectories with tree search and reflection reveals stable atomic structures: indivisible, low-complexity states from which answers can be directly inferred.Atomicity emerges during reasoning rather than being imposed, and the convergence point depends on problem complexity and model capability.
4 Experiments
Experiments evaluate AOT across diverse models, benchmarks, and integrations, finding strong performance, progressive scaling with computation, and modular compatibility with existing reasoning frameworks.
- Experimental Setup: AOT is evaluated on mathematics, code generation, and multi-hop question answering benchmarks using both reasoning and non-reasoning LLM backbones.Reported metrics include pass rates for mathematics and coding tasks and F1 scores for multi-hop QA.
- Main Results: AOT achieves top or highly competitive results across models and benchmarks, including GPT-4o-mini scores of 83.6 on MATH, 95.0 on GSM8K, 75.2 on MBPP, and 68.5 on LongBench.DeepSeek-V3 and DeepSeek-R1 with AOT lead on all reported benchmarks, while O3-mini leads on AIME, LiveCodeBench, and LongBench.
- Scaling and Ablations: Performance improves progressively with additional reasoning iterations, preserving test-time scaling as more computational resources are allocated.The termination strategy is designed to mitigate error propagation from memoryless Markovian transitions.
- Scaling and Ablations: Removing decomposition or DAG-guided contraction significantly degrades performance, with the latter ablation producing a stronger degradation.The ablations respectively omit DAG construction or structural guidance during contraction.
- Integration: AOT uses intermediate Markov states as answer-equivalent entry points for external methods and extends the full Markov sequence into a scaffold for tree search.This modular design supports integration at both single-state and full-sequence granularities.
- Atomic Structure: Deeper chains enabled by tree search and reflection converge toward atomic reasoning paths composed of minimal, non-decomposable problem units.Final-state reasoning tokens increasingly approach the token count of a minimal DAG containing independent subproblems.
5 Conclusions and Future Work
The paper presents AOT as a general-purpose, modular framework for reducing historical dependencies through Markovian transitions and atomic subproblems. Future work centers on aligning this inference-time structure with training objectives, while broader implications concern minimal context, compositionality, and structural modularity.
- Conclusions: AOT alternates decomposition and contraction to reduce complex queries into atomic subproblems for scalable reasoning across mathematics, code, and multi-hop QA.The framework is presented as a plug-in module for existing reasoning paradigms.
- Future Work: AOT’s current implementation operates solely at inference time, leaving alignment of Markovian and atomic reasoning patterns with training-time objectives as future work.Suggested directions include supervised fine-tuning, reinforcement learning, and pretraining on context-isolated reasoning data.
- Broader Direction: The work positions minimal context, compositionality, and structural modularity as foundations for more efficient, interpretable, and robust LLM reasoning.The appendix separately discusses implementation details, empirical analyses, limitations, and broader impacts.
A Implementation Details
The implementation uses domain-specific prompts and a decomposition–contraction workflow to transform reasoning trajectories into self-contained, lower-complexity problems. Prompts also support direct solving, judging, structured DAG dependencies, and task-specific outputs.
- Prompt Structures: AOT uses four prompt types: direct solving, DAG decomposition, question contraction, and LLM-as-a-judge evaluation.These prompts are adapted for mathematical reasoning, code generation, and multi-hop question answering.
- Task-Specific Formatting: The workflow includes task-specific formatting, such as JSON for multi-hop QA and HTML-like answer tags for mathematics and code.Multi-hop QA uses structured outputs containing reasoning chains and supporting evidence, while math and code use clear answer demarcation.
- Decomposition: The decomposition stage represents reasoning as a DAG whose nodes record dependencies on earlier sub-questions or thoughts.Dependencies exclude information directly available from the original question and identify information required from previous sub-questions.
- Contraction: The contraction stage generates a self-contained intermediate problem that requires fewer reasoning steps than the original.Solved independent sub-problems become known conditions, while incorrect explorations can be excluded.
- Code Generation: Code-generation contraction starts from intermediate variables and creates new test cases while preserving the original expected outputs.The simplified formulation avoids code examples and uses intermediate variables as direct inputs.
- Evaluation: The judge prompt compares reference solutions and returns the index of the best solution in zero-based form.This supports solution selection after generating candidate answers.
A.3 Baseline Implementation Details
The baseline implementation adapts established reasoning frameworks for fair comparison across broader task types. It preserves key Forest of Thoughts mechanisms while modifying validity handling and workflow selection.
- Forest of Thoughts: The Forest of Thoughts implementation uses Tree of Thoughts as its tree structure, with majority voting and expert evaluation retained.These mechanisms aggregate results across trees and assess solution quality.
- Forest of Thoughts: Early stopping is removed because rule-based validity checks are less applicable across the diverse evaluation scenarios.The original mechanism is described as particularly effective for constrained tasks such as Game-of-24.
- Forest of Thoughts: The modified Forest of Thoughts implementation reproduces the original scaling curves and achieves superior performance across multiple benchmarks.The stated modifications aim to preserve core strengths while improving adaptability to wider reasoning tasks.
- AFlow: For AFlow, the experiments use the original work’s optimal workflows, including the HotpotQA workflow for LongBench multi-hop reasoning.MATH and GSM8K use their directly identified optimal workflows.
A.3.3 Dataset-Specific Details
The dataset-specific procedure filters MATH for consistent answer formatting and limits evaluation to a selected subset, while evaluating the other benchmarks in full.
- MATH: MATH questions with non-integer or non-decimal answers are filtered out before evaluation.This enforces consistent answer formats for the dataset.
- MATH: The first 1,000 MATH cases are evaluated for efficiency.The passage specifies this subset explicitly.
- Other Benchmarks: The remaining benchmarks are assessed in their entirety.This contrasts with the selected MATH subset.
B Empirical Analysis and Validation
The empirical-analysis section validates the framework through quality, process, and structural analyses. It examines DAG generation, decomposition–contraction examples, and statistical properties.
- Empirical Analysis: The experiments include quality metrics for DAG generation.These metrics assess the generated reasoning structures.
- Empirical Analysis: Concrete examples illustrate the decomposition–contraction process.The examples show how the framework transforms reasoning structures.
- Empirical Analysis: Statistical analyses evaluate structural properties of the framework.The section identifies structural analysis as part of its validation program.
B.1 DAG Generation Quality Assessment
The assessment evaluates whether AOT’s DAG generation and contraction preserve answer equivalence, reduce test-time complexity, and produce states preferred by an LLM judge. Results support reliable, simplifying transitions, illustrated through a three-node mathematical example.
- Transition mechanism: The two-phase transition consists of DAG decomposition followed by contraction, which solves independent subproblems and incorporates their results into the next state.The process is evaluated through answer equivalence and complexity reduction.
- Quality metrics: Answer-equivalence maintenance exceeds 99% across all datasets, indicating that contracted states usually preserve the original question’s answer.The metric compares Qi+1 with Q0.
- Quality metrics: Test-time complexity reduction occurs in 74%-82% of transitions, showing that most transitions achieve meaningful simplification.The metric compares the reasoning complexity of Qi+1 with Qi.
- Quality metrics: LLM-as-a-judge selection rates of 83%-96% indicate that generated states are frequently selected or not rejected over solving the original or decomposed alternatives.The judge chooses among {solve(Qi), solve(Gi), solve(Qi+1)}.
- Worked example: In the example, a depth-3 chain contracts Q0 into a self-contained Q1 that preserves answer equivalence and reduces reasoning steps from 8 to approximately 5.The first transition solves the independent trigonometric subproblem and reformulates the remaining problem.
- Worked example: The example also reduces DAG depth from 3 to 2, leaving the Law of Cosines and difference calculations after the independent subproblem is solved.Further transitions could continue until an atomic state is reached.
B.3 Analysis of Structural Diversity
Analysis of 1,000 MATH questions finds that decomposed solutions usually have moderate depth and a small number of subquestions. Greater structural complexity is associated with lower solution accuracy.
- Structural distributions: Most solution depths fall between 2 and 4, with depth 3 the most common pattern.This distribution motivates the maximum transition count of 3 used in the main experiments.
- Structural distributions: Questions typically decompose into 2 to 5 subquestions, with 3-4 subquestions occurring most frequently.These statistics support the assumption that many problems can be simplified into a small number of subproblems.
- Complexity and performance: As solution-graph depth increases, accuracy generally decreases.The relationship is reported from the Figure 7b scatter plot.
- Complexity and performance: Questions with more subquestions tend to have lower accuracy rates.The relationship is reported from the Figure 7a scatter plot.
- Complexity and performance: Darker points represent more common structural patterns, and high-accuracy solutions mostly occur at moderate depths and subquestion counts.The reported decline in accuracy may reflect error propagation and increased cognitive load in more complex structures.
C Limitations
AOT’s current scope is limited by a fixed transition budget, decomposition overhead, and dependence on the underlying LLM’s ability to generate valid dependency graphs.
- Limitations: The fixed maximum transition count of 3 may not be optimal for every problem type.The paper proposes adaptive settings based on initial DAG depth, while noting that fully dynamic termination would be more robust.
- Limitations: Decomposition adds computational overhead compared with direct inference, creating a trade-off for real-time applications.
- Limitations: Weaker underlying LLMs may struggle to generate valid dependency graphs, potentially degrading performance.