Atom of Thoughts for Markov LLM Test-Time Scaling
Authors: Fengwei Teng
Quan Shi
Zhaoyang Yu
Jiayi Zhang
Yuyu Luo
Chenglin Wu
Zhijiang Guo
Venue: NeurIPS 2025 poster ()
Keywords: LLM Reasoning
Reasoning Framework
Primary area: applications
TL;DR: The Atom of Thoughts leverages a Markovian reasoning process to enhance test-time scaling efficiency in LLMs, decomposing reasoning into low-complexity atomic units for scalable, high-performance inference.

Abstract: Large Language Models (LLMs) achieve superior performance through training-time scaling, and test-time scaling further enhances their capabilities by conducting effective reasoning during inference. 
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 \textit{atomic questions}, exhibiting the memoryless property similar to Markov processes.
Based on this observation, we propose Atom of Thoughts (\our), 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 \textit{decomposition-contraction} process to naturally form a meaningful Markov reasoning process.
Furthermore, these atomic states can be seamlessly integrated into existing test-time scaling methods, enabling \our to serve as a plug-in enhancement for improving reasoning capabilities.

Atom of Thoughts for Markov LLM Test-Time Scaling
Fengwei Teng ? Quan Shi Zhaoyang Yu?, Jiayi Zhang'
Yuyu Luo', Chenglin Wu Zhijiang Guo !HKUST(GZ), DDeepWidoom, RRenmin University of China
Abstract
Large Language Models (LLMs) have achieved significant performance gains through test-time scaling methods. However, existing approaches often incur redun- dant computations due the accumulation of historical dependency information during inference. To address this challenge, we leverage the memoryless property of Markov processes minimize reliance historical context and propose 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 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 series self-contained, low-complexity atomic units. We name this design Atom of Thoughts (AoT). Extensive experiments demonstrate that AoT consistently outperforms existing baselines computational budgets increase. Importantly, AOT integrates seamlessly with existing reasoning frame- works and different L.LMs (both reasoning and non-reasoning), facilitating scalable, nigh-performance inference. We submit our code alongside this paper and will make it publicly available to facilitate reproducibility and future research.
1 Introduction
Large Language Models (LLMs)) exhibit remarkable scaling behavior: as model parameters and training data increase, their performance improves predictably across a wide range of tasks [21]. Recently, test-time scaling methods have emerged push the performance boundary further by increasing computational resources during inference. These range from basic Chain-of-Thoughh (CoT) prompting that extends reasoning chains [33] to more structured approaches like Tree-of- Thought (ToT) [40] and Graph-of-Thour
(GoT) 4 that organize multiple LLM invocations for
exploring solution spaces, and recent reasoning models such as OpenAl O1 26 and DeepSeek
R1 that enhance LLMs' long-chain reasoning ability through post-training 29 24 [8]
9
However, current Tramework-baseee test-time scaling methods typically rely heavily on retaining extensive historical information. Even the simplest CoT must preserve the entire reasoning trajectory to generate each subsequent step 33 Tree-based methods maintain ancestor and sibling relations for branching decisions 40
while Graph-based methods introduce even more complex dependencies through arbitrary node connections 4 (2). Figure Tb analyzes these representative structures and abstract the complexity of historical information and reasoning completion token involved each LLM invocation.
56
To decouple the current problem's 's reasoning from processing historical information and thus mini- mize their mutual interference during test-time computation, we aim to generalize Markov chain- style structures to ceneral-purpose reasoning. By exploiting the memoryless property of Markov pro- cesses, we design the Markovian reasoning process, where each state encapsulates self- cof-aintd
*Corresponding Authors. Contact: stammedbbn222222mmlooooomo
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Queation
Token Comsump tion
Slice cheesea aus A pealtive iinceezzo Bob lists all finice nonerg by peta B of pesitive integera auch that Taa t and these aze 2024 auch aeta. grind (.66))
pousing
06A1
Otnl
Cot thoughts
3.ter any posteive integer the
nurber of nonerpty tinise sete D with
max B a In 2-B-.)
2. a.chozefore the tesal
(RBA)
Poken Conmunpt tonn
drcomponition
2nd 2n5 253.
Hatch each terr 20-3-13 to get the qun 35.
hot
C.Ciculate the aun [4t4 given
shas x_ [REA) 2 (k-11) equala 2024.
2. Caleuilate 11 + 10 9 4
(b)
Figure 1: Token Allocation Comparison in Reasoning Frameworks. Figure (a) demonstrates the differences between thoughts and states, where the red- ood-highlighted text in thoughts reflects dependencies on historical information, whereas states maintain answer-equivalence with the initial problem while progressively reducing execution complexity. Figure (b) illustrates differences in the number of prompt tokens and completion tokens for CoT, ToT, GoT, and the state-based AoT. For simplicity, we assume each thought consists of the same number of tokens, with an average of O(n) thoughts required to express solution. While ToT maintains b branches, resulting in fixed number of invocations per expansion stage, GoT's settings can be flexibly adjusted depending on the scenario and are thus denoted (b)).
problem, thereby significantly reducing historical dependencies. The reasoning process is expressed sequence of states with progressively reduced test-time complexity, rather than an accumulation of historical thoughts like CoT, as illustrated in Figure la To ensure steady progress, we introduce two-phase state transition mechanism: the decomposition stage converts the current state into Directed Acyclic Graph (DAG)-based reasoning path, and the contraction stage uses its structure to reduce dependencies and generate the next state.
This fundamental structure with memoryless property distinguish our approach from many CoT-based methods. Thus, our method can be seamlessly integrated with existing test-time scaling methods, enhancing their scaling efficiency. While exploring integrations with tree search and reflective refinement to further scale up the Markovian reasoning chain, we identify an emergent trend towards an atomic reasoning structure (Figure 4 where reasoning trajectories are represented as a series of self-contained, low-complexity atomic problems. To emphasize this characteristic, we name our approach Atom Thoughts (AoT).
Our contributions are summarized as follows:
Markovian Reasoning Process. We introduce reneral-purpost Markovian reasoning process that achieves high-quality and cost-effective reasoning across various scenarios, including code generation, mathematical reasoning, and multi-step reasoning tasks.
Scalable Reasoning Structure. The basic structure design of Markov chain in AoT facili- tates seamless integration with various test-time scaling methods, significantly enhancing computational efficiency and allowing the combination of different methods' advantages. This scalability ensures more effective utilization of increased computational budgets without the overhead of maintaining extensive historical contexts.
Atomic Reasoning. Further leveraging AOT's seamless integration capability to enhance itself, by integrating with tree search and reflective refinement to scale up the exploration of the Markovian reasoning chain, we uncover an emergent atomic reasoning structure. this structure, complex reasoning trajectories are decomposed into sequence of atomic, self-

---

contained units with low complexity. This atomicization brings about improved reasoning performance and robustness.
2 Related Work
2.1
Reasoning Framework
Drawing inspiration from cognitive behaviors in human reasoning
3 such step-by-step 54]. and aggregation ensem- enhance the reasoning various prompting strategies have been developed
decomposition 33 57
31 13]. reflective refinement 123
55
ble [32 20
42
capabilities of LLMs. These reasoning frameworks typically employ structured representations, including chains, graphs, and trees [40, [1]] to model the reasoning space efficiently and system- atically. Chain-basse methods, for instance, decompose complex problems into linear sequences of subproblems [33 557 BT primarily optimizing for stepwise dependency. contrast, tree- and basph-bsed formalisms support hierarchical exploration of multiple reasoning paths, allowing for more dynamic adaptation during the problem-solving process 44) These structured approaches have demonstrably improved LLM performance in diverse applications like code generation, question
answering, and complex data processing 17 16 48 [5].. by enabling L.LMs to tackle intricate
problems with enhanced coherence and interpretabilityy
While these structured methods significantly expand LLMs' reasoning capabilities, they also inher- ently accumulate historical dependencies. This accumulation can lead to increased computational costs and potential interference during the inference process. Recent efforts have attempted to mitigate this reliance on historical information by exploring Markovian reasoning processes and atomic reasoning steps, aiming for more memoryless transitions [36 34
58 35). However, these approaches often suffer from task-specific design limitations. hindering generalizability and efficient parallelism [2 38 46).. In contrast, AOT introduces DAG-based approach that decouples partial subproblems into atomic nodes. This decoupling enables independent state transitions without the substantial overhead associated with maintaining historical context. By iteratively decomposing problems into these atomic nodes and then contracting them, our method reduces overall complexity and inherently supports efficient parallel execution, thereby addressing the limitations of traditional chain, tree, and graph- based structures.
2.2 Test-Time Scaling
Test-time scaling has emerged as powerful mechanism to enhance LLM reasoning by extending computational effort during inference. Framework-base approaches augment LLM capabilities through structured reasoning extensions, leveraging cognitive operations and external tool integration to facilitate deeper exploration of solution spaces [49 reasoning cycles, recursive problem-solving performance on complex reasoning tasks. Despite these advances, existing techniques commonly preserve full historical state information throughout the reasoning process. This can lead to redundant computational overhead and potential conflicts across successive reasoning steps.
28 7 These methods introduce reflective and dynamic path selection, significantly improving
Recent work has explored alternative strategies, such as supervised fine-tuning on CoT trajectories, demonstrating improved LLM capacity to maintain coherent, long-term reasoning inforcement learning have further pushed these boundaries by enabling models to autonomoully
Re-
extend reasoning chains, potentially unlocking emergent cognitive patterns [2 47 9 45 However, similar to framework-based methods, these techniques often rely on maintaining expansive historical contexts, which can limit their efficiency and scalability as reasoning paths become extended.
In contrast to these history methods, our approach adopts a Markovian perspective, modeling the reasoning process as state transitions assisted by a temporary DAG structure. This memoryless design eliminates the need for redundant history tracking, focusing computational resources solely on current state transformations. Furthermore, our proposed two-phase transition mechanism, comprising decomposition and contraction stages, facilitates atomic problem-solving This enhances computational efficiency while maintaining structural clarity. This structured yet flexible approach not only reduces dependency overhead but also aligns naturally with the principles of test-time scaling, offering seamless integration with existing reasoning frameworks to achieve scalable, high-performance inference.
3

---

thoughte
3/5. Éied
Markov Process
O-O-O-O
possible
Lssaggee aatinlying
Pcee of thoughts
* 3/5 Fisd the possiie
lengtha side
Giveo two tesangins ALC 16, aio a 375, ose respectively. postiiiee difference
alese is 4/5
batrees the langita
Graph thoughte
Let BC Sy, Find the equaciinn sten con +4/h.
b'ral-Mt,- difcnonzce
Porest
16
find betreea and
Figure 2: Overview of AOT. The Markov reasoning framework iteratively derives states Q++ from predecessors Qi using DAG decomposition and contraction. The left part shows this iterative process, while the right part highlights the integration with existing methods. Any intermediate state Q; can act as an entry point Qo for other methods. ensuring flexible composition while preserving answer equivalence to the original question. This allows AoT to operate independently or as preprocessing module to optimize the performance efficiency of existing approaches.
3 Atomic Reasoning via Markov Process
In this section, we first formally derive Markovian reasoning process grounded in clear probabilistic formulation. We then diseuss how this Markovian reasoning structure can be integrated seamlessly with other reasoning methods to further scale up inference time. Finally, we demonstrate how atomic reasoning structures naturally emerge through such scaling-up procedures. The overview of this Markovian reasoning process is illustrated in Figure 2
3.1 Markovian Reasoning Process
Reasoning Chain. CoT reasoning introduces a sequence of intermediate steps T; to solve problem.
This process can be formalized probabilistic sampling procedure:
N
A ~~ P~A(T Qo)
(I)
1=
where A is the final answer, and T (To, ........ Tv} } is the sequence of thoughts, each conditioned on the previous steps Tex and the initial question Qo-
An alternative Cormulation-Leesttte
57
reframes the node of chain as sub-
question Qi yielding:
A p p()12))
2=0
Under the above formulation, the reasoning process is characterized by the accumulation of in- termediate thoughts or subquestions in the sequence, leading continual increase in historical information. However, ideally, the reasoning chain satisfies the property of memoryless Markov process process-where where each state S,+1 depends only on S, we obtain:
N
A~ P(A(S)
II 1=D
((S.+1S)))
(3)
where S; represents state in the Markovian reasoning process. In the following paragraph, will explicitly clarify the semantic content of the Markov state S,, resulting in more specific and practical representation.

---

Markoy State. In practice real-world problems rarely satisfy the strict Markov assumption directly, To establish a meaningful Markovian formulation, we reuse the subquestion symbol Qi to represent the Markov states St initialized by the original question Qo. Since the final answer A must be derivable from the final state Q-1, follows naturally that Q- is answer-equivalent an essential invariant emerges: each intermediate subquestion Q; must preserve answer-equivalence with the original question. To ensure meaningful Markov state transitions, we further impose that the sequence of subquestions {Qo. Q1...., QN) monotonically reduces in complexity, guaranteeing genuine reasoning progress at each transition.
Qo- Thus,
Two-phase Transition However, state transitions aiming at test-time reduction remain challenging for L.LMs, especially without task-specific training. This difficulty arises primarily from the complex historical dependencies within reasoning trajectories. To address this issue, we propose a two-phase transition mechanism that first explicitly decomposes the current state Q; to capture the internal dependencies before contracting them into the next state.
In the decomposition phase, we introduce DAG scaffold G. to explicitly represent the dependency structure among reasoning steps within each intermediate question Q,, This temporary structure is later discarded to eliminate historical dependencies, enabling the Markovian transition. Formally, the DAG is defined as:
9 = EN, E ((N,, k}
(4)
where nodes N₂ represent individual thoughts subquestions, and edges (Nx) indicate that node N, provides necessary information for node No.
In the subsequent contraction phase, we transform the temporary DAG structure G. into the next Markov state Qi+1- Specifically, nodes without incoming edges in G, are independent and can be safely discarded, whereas the remaining dependent nodes are reformulated into an answer-equivalent independent question Qi+I. Formally, the overall Markovian transition process can expressed as:
N
~~ p(A[(N II p(GG))))))))
detailed step-by-step example demonstrating the complete decompasition-cootractiio process is provided in Appendix B.2
3.2 Emerged Atomic Reasoning
The Markovian reasoning process provides fundamental, low-level structural prior for inference. In this subsection, we diseuss the design of a termination mechanism to counteract the potential fragility introduced by strict memorylessness, thereby constructing stable reasoning framework. Moreover, we describe how this Markovian reasoning structure can be combined with additional methoods--arricullarly through structured exploration via search and reflective verification-ta further scale up test-time reasoning. This combined approach reveals the emergence of a stable, indivisible reasoning structure, termed atomic reasoning.
Termination Strategy. Unlike CoT-based approaches, which can recover from early errors by leveraging accumulated context, our Markov chain lacks such fallback due its memoryless nature. This amplifies the risk of propagating low-quality transitions if an intermediate question Q++1 diverges semantically from the original task, subsequent reasoning becomes meaningless.
To address this, we introduce quality-aware termination strategy. After each transition Q: - Qi+1. an I.LM-as-a-judge selects the best answer to the original question Qo from the triplet (solve(Q,). Q.)). solve(G,), solve(Q.+1)). Crucially, this mechanism implicitly enforces answer equiv- alence: if Q.+1 fails to preserve answer equivalence with Qo. then solve(Q:+1) will not provide valid answer for Qo and thus cannot be selected by the judge. This selection- based filtering naturally ensures that only semantically stable transformations maintaining answer equivalence retained. If Qi+1 is not selected, the process terminates and returns the best candidate among the three. Detailed quality metrics demonstrating the effectiveness of this mechanism are provided in Appendix
Modular Integration. Since each Markov state is constrained to be an equivalently transformed representation of the original question, the reasoning process forms semantically aligned and
5

---

Table 1: Performance Comparison.
Model
Benchmark
CoT
CoT-SC
SR
AR
AFlow
ToT
GoT
FoT
AoT
Non-Rensoning LLMs
MATH
78.3
81.8
78.7
65.4
83.0
82.0
82.3
82.6
83.6
GPT-to-mini
GSM8K
90.9
92.0
91.7
87.2
93.5
91.8
92.1
94.2
95.0
MBPP
72.4
73.2
72.8
LongBench
57.6
58.6
58.2
52.9
61.0
59.0
59.2
60.8
68.5
MATH
94.4
95.2
94.8
90.1
96.1
95.0
95.3
95.6
96.5
DeepScek-V3 V3
GSM8K
96.2
97.0
96.8
92.5
97.8
96.5
96.8
97.5
98.2
MBPP
75.7
76.5
77.3
LangBench
58.8
60.1
59.5
55.3
63.5
61.2
61.5
63.3
71.0
Reasoning LLMs
79.6
O3-mini
LiveCodeBendl
23.6
25.0
24.2
20.0
26.5
25.2
25.5
27.8
32.2
LongBench
56.3
57.5
56.8
52.0
58.0
57.9
65.3
AIME
78.3
79.7
78.9
74.7
81.2
79.9
80.2
80.5
81.7
DeepSeek.BR
LincChdeBench
25.9
LongBench
55.1
56.2
55.4
52.3
58.7
57.0
57.5
58.2
67.9
fully self-contained sequence problem representations. This property enables modular reasoning without compromising the integrity of the overall task. In practice, each state within the chain be independently routed to specialized solvers, subjected to verification proceuues, or further embedded tree-based graph-based inference. The introduction
into structured reasoning frameworks-such of the Markov reasoning process thus does not merely offer an alternative to previous reasoning chain methods, but rather defines structural foundation upon which diverse test-time reasoning strategies can be constructed.
Atomic Structure. Although the termination strategy ensures robustness, it also restricts the emergence of deeper reasoning chains. To explore the full potential of the Markov process, sample and extend trajectories, combining tree search and reflection mechanisms. These structured explorations reveal statistically supported phenomenon: deeper reasoning states tend converge into irreducible forms, maintaining a stable and relatively low reasoning token count, from which the original problem's 's answer can be directly inferred with high execution stability. We refer to these stable forms as atomic structures: indivisible and self-contained representations that require no further decomposition. Importantly, atomicity not imposed a priori, but emerges naturally as property discovered throughout the reasoning process. This convergence toward atomic units represents a logical endpoint where problems become sufficiently simple that further decomposition is neither necessary nor beneficial. Notably, this convergence point is jointly determined by both the intrinsic complexity of the problem and the reasoning capabilities the underlying model model-different problems may converge at different depths, and the same problem may exhibit different atomic granularities when solved by models with varying capacities.
4 Experiments
Our experiments aim two primary objectives. First, we conduct main experiments across variety of datasets spanning mathematics, code generation, and multi-hop question answering to demonstrate the cost-efficiency advantages AoT the flexibility provided by the basic Markov chain structure in our approach, we design integration experiments at various granularities. These experiments explore the utilization of AOT as plug-in component to enhance cost-efficiency in other reasoning frameworks and investigate scaling effects in integration with classical methods like tree search and verification- based reflection, analyzing emergent reasoning phenomena.
purrpoe-purpose reasoning framework. Second, leveraging

---

MATH
GSMBX
LongBench
Accurary
62
60
60
76
Cost [080, log 2 soale)
Cost (USD, log 2 ocalel
Coat (DSD, log scale)
AIME
Li LiveCodaBench
Aocurary
-3 Cost (0SD, log scalo)
-2 Cost (U8D, log s0s1e)
w//terompooltionn
Alley
Figure 3: A comparison of performance and cost of various methods and ablation methods on the dataset, with GPT-4o-mini the backbone. Each node in the curves represents AoT (or ablation variants) iteration result, where increasing token consumption indicates deeper iterations. Due to relatively poor AR performance leading to scattered data points, AR data points excluded.
4.1 Experimental Setup
Benchmarks and Metrics. We AoT across representative benchmarks covering mathemat-
ical reasoning (MATH (14), GSM8K [8], AIMI!", code generation (MBPP []] LiveCodeBench [19
and multi-hop question answering tasks (HotpotQA [39], MuSiQue 33), and 2WikiMultHHoPAA [I5]
preprocessed by LongBench (2), see Appendix F.3 for details. Following previous work [49] 5 we
report pass rates for mathematical and coding benchmarks, and F1 scores for multi-hop QA tasks.
Settings. All prompt templates used in Markov reasoning process for experiments are fully de- scribed in Appendix A.1 Key hyperparameters. including model temperature and Markov chain length, are detailed and discussed in Appendix A.2 We the default temperature 1.0 and the maximum Markov chain length to for the main experiments to balance performance and efficiency while enabling scaling curves. Due to AOT design and termination mechanism, longer chain lengths increase the performance ceiling without linearly increasing costs.
Backbones and Baselines. AoT is designed to be compatible with various LLM backbones. To demonstrate its effectiveness, we employed two categories of LLMs. The first category comprises non-reasoning LLMs, specifically GPT-4o-mini [25] and DeepSeek-V3 [0O] The second category includes reasoning-capable LLMS such as O3-mini
27 and DeepSeek RI
9
Specifically, we
MATH, GSM8K, and MBPP, and reasoning- capable models to evaluate performance on more challenging tasks such as AIME and LiveCodeBench. Additionally, since multi-hop QA is not primary focus for reasoning-cape capable models, both categories of models are evaluated on LongBench for comprchensive comparison.
non-reasoning models evaluate performance
For comparison, we evaluated AoT against diverse set of baseline methods, broadly categorized by their interaction pattern with the L.LM: single-call or multi-call invocations. Single-call approaches include well-known techniques like Chain-of-Thought (CoT) [33] and Chain-of-Draft (CoD) [37].
Multi-call methods represent more complex workflows, such as CoT with Self-Consistency (CoT-
SC) [32], Self-Refine (SR) 23 Analogical Prompting (AP) AK Forest-of- -houghh (FoT) [5], and
agentic framework AFlow
Further details are provided Appendix
hung:///nngiignneeewwwasssssaaaa 2024
7

---

4.2
Main Results
Table presentss the main experimental results. Across both Non-Reasoning and Reasoning LLMs, AOT consistently demonstrates strong performance. For Non-Reasoning LLMs such GPT-4o-mini and DeepSeek-Ve -V3, AOT achieves the highest scores on benchmarks like MATH, GSM8K, MBPP, and LongBench, often surpassing all other compared methods. For instance, with GPT-40-mini, AOT scores 83.6 on MATH, 95.0 on GSM8K, 75.2 on MBPP, and 68.5 on LongBench, which are the top performances. Similarly, DeepSeck-V3 V3 with AOT leads with scores on all benchmarks.
In the Reasoning LLMs section, featuring 03-mini and DeepSeek-RI. AoT continues to exhibit competitive and often leading performance, For 03-mini, AoT achieves the highest scores on AIME (83.0), LiveCode (32.2), and LongBench (65.3). With DeepSeek- RI, AoT again leads on all tasks. Overall, AoT consistently achieves diverse set of models and benchmarks, demonstrating its effectiveness.
or highly competitive results across a
Figure further demonstrates that performance improves progressively with additional reasoning iterations. This highlights the effectiveness of our proposed termination strategy: by mitigating error propagation from memoryless Markovian transitions, it preserves the desirable test-time scaling perfery---e does not degrade more computational resources are allocated.
4.3 Ablation Study
We conduct ablation studies to examine the impact of core components in our framework. Specifically, we evaluate two variants: (1) Without Decomposition, where the model directly contracts reasoning trajectories from the initial question without constructing DAG; and (2) Without DAG- Contraction, where decomposition still occurs, but the contraction step does not rely on any structural guidance. In this setting, only the first naturally independent subproblem is separated out. Figure shows that both ablations significantly degrade performance, with the second variant causing a more severe drop. This suggests that partial superficial structural cues can be more harmful than providing none at all. These results underscore the importance of explicitly modeling fine- ame-grained dependencies in reasoning trajectories, showing that faithful structural representations meaningfully enhance reasoning effectiveness and precision. Comprehensive quality metrics for the DAG generation process, including answer equivalence maintenance rates (>99% across all datasets) and complexity reduction rates (74-82%), are provided in Appendix B.1
4.4 Scaling Up Analysis
In this section, we further explore the scalability of AOT by integrating it with existing reasoning frameworks, leveraging its flexible, modular design. We begin our analysis by using individual Markov states as integration points-a lightweight and straightforward approach where interme- diate states processed by AOT serve as optimized entry points for other reasoning methods. Our experiments reveal substantial efficiency improvements test-time, which encourages us to examine larger, more structured integration granularities to fully capitalize on the structural strengths of our framework. Notably, as we progressively extend the Markov chain during scaling analysis, we observe consistent reduction in the number of tokens required for reasoning in the final states. Through detailed analysis, we identify emerging atomic characteristies the reasoning trajectories, motivating us to design further scaling-up experiments based on this property.
State Integration. The Markov states Q, generated by AOT represent simplified, yet answer- equivalent reformulations of the original questions, making them ideal entry points for external methods. Indeed, AOT itself demonstrates such modular integration potential, employing basic CoT-style prompting to solve each intermediate state. To experimentally validate the effectiveness of these intermediate states, we investigate whether initiating reasoning using optimized intermediate states Q1 can enhance both accuracy and computational efficiency in external frameworks. The results, illustrated in Fi confirm that starting reasoning from these optimized intermediate states notably improves performance while simultancously reducing computational costs, as demonstrated in the integration with frameworks such as FoT.
Tree Searching. Beyond single-state integration, the full Markov sequence Q generated by AOT can provide structured scaffold for more complex reasoning frameworks, effectively replacing
8

---

Integration Peccomanne
Acoic Stoucture Cosveeppoce
2.1
2.3
14
6.7
13.3
1.4
3.2
36.7
Blay
Atonde
Jedlective Recineeent
F-t Hackor
Hazkor dhain
Figure 4: The process involves gradually enhancing integration for scaling up at test time. ToT uses three branches, while FoT employs two, four, and eight trees, respectively.
traditional CoT-based structures. In conventional CoT-based ToT, the inherent randomness of LLM- based sampling can lead to inconsistencies in reasoning chain lengths, causing nodes at the same depth represent varying stages of reasoning progress. This inconsistency complicates node comparison and diminishes pruning effectiveness. In contrast, the Markov chains constructed by AoT ensure answer equivalence between each intermediate node and the original question, thereby guaranteeing fundamental comparability across nodes at the same depth. This structural consistency significantly enhances the gains from scaling through parallel sampling at test-time.
Reflective Refinement. Termination strategy in AOT provides safeguard for the quality of single-pass Markov reasoning. When a transition yields a low-quality intermediate state, early termination allows the system to avoid wasting computation conservative mechanism may also limit further exploration. To address this, we augment our method with verification-basee reflection, where transitions Q, Q++1 evaluated by an LLM-as-a- judge to assess whether the newly generated state exhibits a significant degradation in test-time performance. If such degradation is detected, the system triggers reflective refinement step, encouraging deeper and more meaningful reasoning rather than trivial reformulations. This reflective verification substantially improves comparability between nodes the same depth, increases the effective exploration space, and further amplifies the benefits structural scaling. When combining all three integration strategies (ToT Markov chain Reflective Refinement), we observe significant performance gains: for instance, on MATH, this full integration achieves 84.9% accuracy compared ToT's 82.0%, and on AIME, it reaches 81 31.2% versus ToT's 78.0%, demonstrating the compounding benefits of our modular design.
unpromising paths. However, this
Atomic Struture. Due to the inherent scalability of the AOT architecture, deeper Markov chains enabled by both tree search and verification- based reflection eexiiit stronger test-time performance and require fewer reasoning tokens the final state. Statistical analysis reveals that the token count of final reasoning steps gradually approaches that of minimal DAG representation comprising all independent subproblems generated during transitions. This suggests a natural convergence toward atomic ciates-questions that are semantically represent indivisible reasoning units. We refer to this phenomenon as atomic reasoning, where the entire reasoning trajectory is composed of such minimal, non-decomposable elements. To further validate this insight, we conduct additional experiment where we isolate and re-cxecute these highly atomic reasoning paths independently. While this incurs significantly higher computational cost, the results exhibit stable scaling trends, highlighting the structural advantages of AOT with high budget.
Conclusions and Future Work
We present AOT, general-purpose purpose reasoning framework that leverages Markovian transitions to minimize historical dependencies during inference. By altermating between decomposition and contraction, AOT incrementally reduces complex queries into atomic subproblems, enabling scalable and modular reasoning across maths, code, and multi-hop QA tasks. Empirically, we show that AOT not only scales gracefully with compute but also integrates flexibly into existing reasoning paradigms plug-in in module. Limitations and broader impacts of AOT are provided in Appendix ?? and ??.

---

While AoT offers promising path toward atomic reasoning. its current inplementation operates solely inference time. A natural extension to align this structure with training-tims objec- tives tives-teaching models to internalize Markovian and atomic reasoning patterns directly. This could involve supervised fine-tuning with synthetic traces, reinforcement learning over decomposition trajectories, or pretraining on datasets that promote context-isolated reasoning.
More broadly, this work lays the foundation for reasoning systems that emphasize minimal context, compositionality, and structural modularity. We hope AOT serves as a stepping stone toward more efficient, interpretable, and robust reasoning with large language models.
References
[1] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. Program synthesis with large language models. arXiv preprint arXiv:2108.077333 07732, 2021.
[2] Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, Yuxiao Dong, Jie Tang, and Juanzi Li. Longbench: A bilingual, multitask benchmark for long context understanding. In ACL (7), pages 3119-3137. Association for Computational Linguistics, 2024.
[3] W. Bechtel, A. Abrahamsen, and G. Graham. Cognitive science: History. In Neil J. Smelser and Paul B. Baltes, editors, International Encyclopedia of the Social & Behavioral Sciences, pages doi: https://doi.org//0.1001 B0-008-043307--770144--- URL http::ttp///// www. http://wwwweeeeeeeeeeetcccc wwtp:/eweett.cc..eeeeeeeeeeeeeee http://t.cccecccceeeee/eer.iiaat p11/8008043006701442X
2154-2158. Pergamon, Oxford, 2001. ISBN 978-0-08-044076-8
[4] Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler. Graph of thoughts: Solving elaborate problems with large language models. In AAAI, pages
AAAI Press, 2024.
[5] Zhenni Bi, Kai Han, Chuanjian Liu, Yehui Tang, and Yunhe Wang. Forest-of-thought: Scaling test-time compute for enhancing LLM reasoning. CoRR, abs/2412.00 12.09078, 2024.
[6] Edward Y. Chang, Yuxuan Tong, Morry Niu, Graham Neubig, and Xiang Yue. Demystifying long chain-of-thooe of-thhuuhttt reasoning in llms. CoRR, hass/2502.03733. 2025.
[7] Lingjiao Chen, Jared Quincy Davis, Boris Hanin, Peter Bailis, Ion Stoica, Matei Zaharia, and James Zou. Are more LLM calls all you need? towards scaling laws of compound inference systems. CoRR, Abss22403.02419, 2024.
[8] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. CoRR, abs/21 14.14168, 2021.
[9] DeepScck-AL. Deepseck-rl: Incentivizing reasoning capability in Ilms via reinforcement learning, 2025. URLpsttss///rxii org/ http//bb/22501.1 12948
[10] DeepSeek-AI, Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Daya Guo, Dejian Yang, Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, Guangho Hao, Guanting Chen, Guowei Li, H. Zhang, Han Bao, Hanwei Xu, Haocheng Wang. Haowei Zhang, Honghui Ding, Huajian Xin, Huazuo Gao, Hui Li, Hui Qu, J. L. Cai, Jian Liang, Jianzhong Guo, Jiaqi Ni, Jiashi Li, Jiawei Wang, Jin Chen, Jingchang Chen, Jingyang Yuan, Junjie Qiu, Junlong Li, Junxiao Song, Kai Dong, Kai Hu, Kaige Gao, Kang Guan, Kexin Huang, Kuai Yu, Lean Wang, Lecong Zhang, Lei Xu, Leyi Xia, Liang Zhao. Litong Wang. Liyue Zhang, Meng Li, Miaojun Wang. Mingchuan Zhang, Minghua Zhang. Minghui Tang, Mingming Li, Ning Tian, Panpan Huang, Peiyi Wang, Peng Zhang, Qiancheng Wang, Qihao Zhu, Qinyu Chen, Qiushi Du, R. J. Chen, R. L. Jin, Ruiqi Ge. Ruisong Zhang, Ruizhe Pan, Runji Wang, Runxin Xu, Ruoyu Zhang, Ruyi Chen, S. S. Li, Shanghao Lu, Shangyan Zhou, Shanhuang Chen, Shaoqing Wu, Shengfeng Ye, Shengfeng Ye, Shirong Ma, Shiyu Wang, Shuang Zhou,
10

---

Shuiping Yu, Shunfeng Zhou, Shuting Pan, T. Wang. Tao Yun, Tian Pei. Tianyu Sun, W. L. Xiao, and Wangding Zeng. Deepseek-v3 technical report. CoRR, abs/2412.19437,, 2024, doi: 148550/arkee 2412. 19437
11.4800AARXII.242.1999553 URL https::/dt...oorreeeeeee
[11] Ruomeng Ding, Chaoyun Zhang, Lu Wang, Yong Xu, Minghua Ma. Wei Zhang. Si Qin, Saravan Rajmohan, Qingwei Lin, and Dongmei Zhang. Everything of thoughts: Defying the law of penrose triangle for thought generation. In ACL (Findings), pages 1638-1662. Association for Computational Linguistics, 2024.
[12] Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with language model is planning with world model. In EMNLP, pages 8154- 8173. Association for Computational Linguistics, 2023.
[13] Shibo Hao, Yi Gu, Haotian Luo, Tianyang Liu, Xiyan Shao, Xinyuan Wang. Shuhua Xie, Haodi Ma, Adithya Samavedhi, Qiyue Gao, Zhen Wang, and Zhiting Hu. LLM reasoners: New evaluation, library, and analysis of step-by-step reasoning with large language models. In First Conference Language Modeling, 2024. URL httpt://opppeeeeeeeeee wetpe/rreiie.ee//frrnnn. net/forum? id=bOyffSSUGO
[14] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Bric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. In NeurlPS Datasets and Benchmarks, 2021.
[15] Xanh Ho, Anh-Khoa Duong Nguyen, Saku Sugawara, and Akiko Aizawa. Constructing A multi-hop QA dataset for comprehensive evaluation of reasoning steps. In COLING, pages 6609-6625. International Committee on Computational Linguistics, 2020.
[16] Sirui Hong. Yizhang Lin, Bang Liu, Bangbang Liu, Binhao Wu, Ceyao Zhang, Chenxing Wei, Danyang Li, Jiaqi Chen, Jiayi Zhang, et al. Data interpreter: An Ilm agent for data science. arXiv preprint arXiv:2402. 18679, 2024.
[17] Sirui Hong, Mingchen Zhuge, Jonathan Chen, Xiawu Zheng, Yuheng Cheng, Jinlin Wang, Ceyao Zhang. Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, Chenyu Ran, Lingfeng Xiao, Chenglin Wu, and Jürgen Schmidhuber. Metagpt: Meta programming for A multi-agent collaborative framework. In ICLR. OpenReview.net, 2024.
[18] Zhenyu Hou, Xin Lv, Rui Lu, Jiajie Zhang, Yujiang Li, Zijun Yao, Juanzi Li, Jie Tang, and Yuxiao Dong. Advancing language model reasoning through reinforcement learning and inference scaling. CoRR, abs/2501.11651. 2025.
[19] Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Ar- mando Solar- Lezama, Koushik Sen, and lon Stoica. Livecodebench: Holistic and contamination free evaluation of large language models for code. In The Thirteenth International Conference on Learning Representations, 2024.
[20] Dongfu Jiang, Xiang Ren, and Bill Yuchen Lin. LIm-blender: Ensembling large language models with pairwise ranking and generative fusion. In ACL (!), pages 14165-14178. Association for Computational Linguistics, 2023.
[21] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. CoRR, abs/2001.0832 2020.
[22] Kimi, Angang Du, Bofei Gao, Bowei Xing, Changjiu Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, Chenzhuang Du, Chonghua Liao, et al. Kimi kl. 5: Scaling reinforcement learning with llms. arXiv preprint arXiv:2501.12590 2025.
[23] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self-feedback. In NeurIPS, 2023.
11

---

[24] Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi,
Luke Zettlemoyer, Percy Liang, Emmanuel J. Candès, and Tatsunori Hashimoto. sl: Simple test-time scaling. CoRR, abs/2501. 193923 2025.
[25] OpenAL. Gpt-4o mini: advancing cost- intelligence, 2024, URL htttp:://ppppntt
[26] OpenAL. Introducing openai o1, 2024. UtL/tttps://ppeeaa.coo
[27] OpenAI. OpenAl 03-mini: Pushing the frontier of cost-effective reasoning, 2025. URL htttps://openal wwom/inde////e -owpdde/opeeaiioommiiee
[28] Jon Saad-Falcon, Adrian Gamarra Lafuente, Shiok Natarajan, Nahum Maru, Hristo Todorov, Etash Guha, Estefany Kelly Buchanan, Mayee F. Chen, Neel Guha, Christopher Ré, and Azalia Mirhoseini. Archon: An architecture search framework for inference-tine techniques. CoRR, abs/2409.15254, 2024.
[29] Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling L.LM test-time compute optimally can be more effective than scaling model parameters. CoRR, abs/2408.03314. 2024.
[30] Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. Musique Multihop questions via single-hop question composition. Trans. Assoc. Comput. Linguistics. 10:539-555 554, 2022.
[31] Lei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu, Yunshi Lan, Roy Ka-Wei Lee, and Ee-Peng Lim. Plan-and-solve prompting: Improving zero-shot chain-of-thought reasoning by large language models. In ACL (!), pages 2609-2634, Association for Computational Linguistics, 2023.
[32] Xuezhi Wang. Jason Wei, Dale Schuurmans, Quoc V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In ICLR. OpenReview.net, 2023.
[33] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. Chain-of-thougee prompting elicits reasoning in large language models. In NeurIPS, 2022.
[34] Kun Xiang, Zhili Liu, Zihao Jiang, Yunshuang Nie, Runhui Huang, Haoxiang Fan, Han- hui Li, Weiran Huang, Yihan Zeng, Jianhua Han, Lanqing Hong. Hang Xu, and Xiaodan Liang. Atomthink: A slow thinking framework for multimodal mathematical reasoning. CoRR, abs/2411.1 2024.
[35] Kun Xiang, Zhili Liu, Zihao Jiang, Yunshuang Nie, Kaixin Cai, Yiyang Yin, Runhui Huang, Haoxiang Fan, Hanhui Li, Weiran Huang, et al. Can atomic step decomposition enhance the self-structured reasoning of multimodal large models? arXiv preprint arXiv:2503.06252 2025.
[36] Amy Xin, Jinxin Liu, Zijun Yao, Zhicheng Lee, Shulin Cao, Lei Hou, and Juanzi Li. Atomr: Atomic operaeer-empoowree large language models for heterogeneous knowledge reasoning. CORR, 1. 2024.
[37] Silei Xu, Wenhao Xie, Lingxiao Zhao and Pengcheng He. Chain of draft: Thinking faster by writing less. CoRR, abs/2502. 18600, 2025. doi: 10.48550/ARXIV2502.210 18600. URL
https:///oi.org/ 10w500...8500/////. /005550/aXXi.... 2502. 18600
[38] Wen Yang, Kai Fan, and Minpeng Liao. Markov chain of thought for efficient mathematical reasoning, CoRR, abs/2410. 2024.
[39] Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W. Cohen, Ruslan Salakhut- dinov, and Christopher D. Manning. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. In EMNLP, pages 2369-2380. Association for Computational Linguistics, 2018.
[40] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In NeurIPS, 2023.
12

---

[41] Xinhao Yao, Ruifeng Ren, Yun Liao, and Yong Liu. Unveiling the mechanisms of explicit cot training: How chain-of- of-thought enhances reasoning generalization. CoRR, abs/2502.04667, 2025.
[42] Yuxuan Yao, Han Wu, Mingyang LIU, Sichun Luo, Xiongwei Han, Jie Liu, Zhijiang Guo, and Linqi Song. Determinnetthen-ensembbe ensembling. In The Thirteenth International Conference on Learning Representations, 2025.
Necessity of top-k union for large language model
URL URLptspp://pppereviie net/ wow.mmmmddoDDnnnnnnnuu
[43] Michihiro Yasunaga. Xinyun Chen, Yujia Li, Panupong Pasupat, Jure Leskovec, Percy Liang, Ed H. Chi, and Denny Zhou. Large language models as analogical reasoners. In ICLR. OpenReview.net, 2024.
[44] Yixin Ye, Zhen Huang. Yang Xiao, Ethan Cher, Shijie Xia, and Pengfei Liu. Limo: Less is more for reasoning. arXiv preprint arXIv:2502.033887,20 2025.
[45] Qiying Yu, Zheng Zhang, Ruofei Zhu, Yufeng Yuan, Xiaochen Zuo, Yu Yue, Tiantian Fan, Gaohong Liu, Lingjun Liu, Xin Liu, et al. Dapo: An open-source Ilm reinforcement learning system scale. arXiv preprint ar arXiv:2503. 14476, 2025.
[46] Oussama Zekri, Ambroise Odonnat, Abdelhakim Benechehab, Linus Bleistein, Nicolas Boullé, and levgen Redko. Large language models as markov chains. CoRR, abs/2410.02724, 2024.
[47] Weihao Zeng, Yuzhen Huang, Qian Liu, Wei Liu, Keqing He, Zejun Ma, and Junxian He. Simplerl-zoo: Investigating and taming zero reinforcement learning for open base models in the wild. arXiv preprint arXiv:2503.18892 2025.
[48] Guibin Zhang, Kaijie Chen, Guancheng Wan, Heng Chang, Hong Cheng, Kun Wang, Shuyue Hu, and Lei Bai. Evoflow: Evolving diverse agentic workflows on the fly. CoRR, abs/2502.073373, 2025.
[49] Jiayi Zhang, Jinyu Xiang, Zhaoyang Yu, Fengwei Teng, Xionghui Chen, Jiaqi Chen, Mingchen Zhuge, Xin Cheng, Sirui Hong, Jinlin Wang, et al. Aflow: Automating agentic workflow generation. arXiv preprint arXiv:2410.1077 2024.
[50] Jiayi Zhang, Chuang Zhao, Yihan Zhao, Zhaoyang Yu, Ming He, and Jianping Fan. Mobileex- perts: A dynamic tool-enabled agent team in mobile devices. arXiv preprint arXiv:2407.03913 2024.
[51] Jinghan Zhang and Kunpeng Liu. Thought space explorer: Navigating and expanding thought space for large language model reasoning. In 2024 IEEE International Conference Big Data (BigData), pages 8259-88-0 8251. IEEE, 2024.
[52] Yifan Zhang, Yang Yuan, and Andrew Chi-Chih Yao. On the diagram of thought. CoRR, 100388 2024.
[53] Zhuosheng Zhang, Aston Zhang, Mu and Alex Smola. Automatic chain of thought prompting large language models. In ICLR. OpenReview.net, 2023.
[54] Chuanyang Zheng, Zhengying Liu, Enze Xie, Zhenguo Li, and Yu Li. Progressive- hint prompt- ing improves reasoning in large language models. CoRR, abs/2304.09797, 2023.
[55] Huaixiu Steven Zheng, Swaroop Mishra, Xinyun Chen, Heng-Tze -ze Cheng, Ed H. Chi, Quoc Le, and Denny Zhou. Take step back: Evoking reasoning via abstraction in large language models. In ICLR. OpenReview.net, 2024.
[56] Andy Zhou, Kai Yan, Michal Shlapentokh-Rothhnn Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning, acting, and planning in language models. In ICMI.. OpenReview.net, 2024.
[57] Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoe V. Le, and Ed H. Chi. Least-to-most prompting enables complex reasoning in large language models. In ICLR. OpenReview.net, 2023.
13

---

[58] Pei Zhou, Jay Pujara, Xiang Ren, Xinyun Chen, Heng- Tze Cheng, Quoc V. Le, Ed H. Chi, Denny Zhou, Swaroop Mishra, and Huaixiu Steven Zheng. SELF-DISCOVER: large language models self-compose reasoning structures. In NeurIPS, 2024.
Appendix Overview
This appendix is organized into three main parts: Section A provides comprehensive implementation details including prompts, hyperparameters, and baseline configurations; Section presents detailed empirical analyses validating our framework's effectiveness; and Sections ??-?? discuss limitations and broader impacts of this work.
A Implementation Details
This section provides comprehensive implementation details necessary for reproducing our experi- ments, including prompt templates, hyperparameter settings, and baseline method configurations.
A.1 Prompt Templates
We present the core prompt structures used in AOT for different task domains. Our framework employs four key prompt types: (1) direct for solving problems, (2) decompose for extracting DAG structures, (3) contract for generating simplified questions, and (4) judge for LLM-as-a- judge evaluation. Below we detail domain-speciff implementations for mathematical reasoning, code generation, and multi-hop question answering.
Design Rationale. The Multi-hop QA prompts use JSON for structured responses, while Math and Code tasks use HTML-like tags (c.g., <answer></ansee This design choice reflects task-specific requirements: JSON naturally accommodates Multi-hop QA's need for structured outputs including reasoning chains and supporting evidence, while HTML tags provide clear answer demarcation for Math and Code tasks. Function parameters also vary by domain-Mull Multi-hop QA requires context passages, Code generation needs test cases and dependency information, while Math tasks only require the question. These variations align with the inherent characteristics of each problem type rather than representing arbitrary design choices.
A.1.1 Mathematical Reasoning
def direct (questioo: str):
instruction uen
You are precise math question solver. Solve the given math question step by step using a standard algebraic approach:
QUESTION: (question)
You can freely reason in your reaponse, but please enclose the final ansver within <ansver></anawe tags (pure number without units and explanations)
oen
prompt instruction format (question=questionn)
return prompt
def decompose():
instruction .*.
Decompose the previous reasoning trajectory into series of sub sub-questions or thoughts.
Instructions:
1. Each sub- sub-question or thought should list its other sub- questions or thoughts' indezes it depends ba-eas can be an empty list)
14

---

2. Dependencies are defined as information needed in sub- question thought that:
Does NOT come directly from the original question
MUST come from previous sub- sub-questions or thoughts
return instruction
def contract():
instruction
Generate simplified intermediate form of the original question based the previous sub- uub-questions thoughts step by step.
The previous sub qubstusssoons or thoughts with marked dependencies actually form a directed acyclic graph (DAG), where nodes whose dependencies is empty list be regarded independent sub-questions or thoughts.
The simplified question must be:
1. colf-containdd: The simplified question's 's description must contain all information needed to solve itself, without requiring additional information from the original question or reasoning trajectory
2. test-time reduced: The simplified question must require fewer reasoning steps compared to the original question (these steps are reduced because these solved independent sub-problens or thoughts become known conditions in the simplified question or excluded as incorrect explorations)
... formatter "Last step, enclose the question within <question></ question> tags"
instruction += formatter
return instruction
def (quessiin:: str, solutions: list): instruction
Here is the original problem: (question)
Here are some reference solutions: {solutions}
Ensemble the best answer the original problem from solutions step by step:
formatter = "Last step, enclose the answer within <answer></ansver tags (must be integer or decimal number without units and explanations)*
instruction formatter
solutions_str for i, solution in enumerate (solutions): solutions_ str f'souution {i): [solution)An
prompt instruction format (question=question solutions= solutions_str return prompt
Listing Math
A.1.2 Code Generation
def direct (question: str, contexts: str);
15

---

instruction
Solve the following problem step by step:
{question)
Your code should be python function with format: (contexts)
Please extend your reasoning process much possible; the longer the chain of thought, the better.
formatter = "Last step, enclose your code within "'pyhhon and
instruction formatter
prompt instruction format (qusstion=question, contexts==conextes) return prompt
def decompose instruction .*.
Decompose the previous reasoning trajectory into series of sub questiess or thoughts.
Instructions:
1. Each sub- qub-question or thought should list its other sub- questions or thoughts' indexes it depends (0-based, can be an empty list)
defined information needed in sub- question or thought that:
2. Dependencies
Does NOT come directly from the original question MUST come from previous sub-questions or thoughts
return instruction
def contract (dag, test_cases):
instruction Generate simplified intermediate form of the original problem based on the variable dependency analysis.
You ast arg given a directed acyclic graph (DAG) representing the dependencies between variables in the original code: (dag)
And the original test cases: (test_cases)
The simplified problem 1. Self contaoinee The description must contain all information needed to solve itself, without requiring additional context from the original problem
2. Test-time reduced: The simplified problem require
fever reasoning steps by using intermediate variables from the original code as direct inputs
Your task is Create simplified version the problem that starts with intermediate variables as inpute
2. Generate new test cases that use these intermediate variables as parameters while maintaining the exact same expected outputs in the original teat
Do not use any code examples in your simplified problem formulation.
formatter "EEcloae the simplified problem within <question></ question>> tag and the new test cases (assert codes, use \n to split each case) within <test></teat> tag" instruction += formatter
16

---

prompt instruction format (dag=dag, test_casso-test_cag return prompt
def judge(question, str, solutions: list);
instruction
Here is the original problem:
{queation)
Here are some reference solutions: (solutions)
Give the index of best solution as your answer.
formatter = "Last step, enclose the anaver within <ansuer></ansver tags (0-based)"
instruction formatter
solutions_stz
for 1, solution in cnneeratesooluiong. solutions_ +- f"solution (i): (solution)An"
prompt instruction format (question=question solutions- solutions_str)
return prompt
Listing 2: Code
A.1.3 Multi-hop Question Answering
def direct (quesiiq:: str, contexts: str):
instruction
Solve the following multi question step by step: (question)
CONTEXTS: {contexts}
Pirstly, you need to extract the relevant supporting sentences from the original text, then cut out the continuous segments as the answer.
formatter Rn*
Provide your response this JSON format:
{{
"question": {question},
"thought"; "give your step by step thought process here", susporttingseenennees
Include ALL sentences needed to justify your answer", Use for long sentences when appropriate"
1.
following the instructions above" or "none" no answer can found }}
"answer": "Your precise
instruction formatter
prompt instruction. format (question=question,, contexts=contexta) return prompt
def decompose (question: str, trajectory: str, answer: str): instruction "*.
You are tasked with breaking a multiple choice question reasoning process into sub-questions.
Original Question: {question)
17

---

Complete Reasoning Process: (trajectory)
Instructions:
1. Break down the reasoning process into a series of sub- questions
2. Each sub-question should:
Be written in interrogative form
Have a clear answer
List its other sub sub-questiona' indexes it depends (0-based can be an empty list)
defined information needed to the current sub qub-question that:
3. Dependencies
Does NOT come directly from the original question
MUST come from the answers of previous sub que-ques
formatter
Format your reaponse as the following JSON object:
{
"thought": "<the thought process of how to step by step propose the sub questions until the ansver of the original question in given reasoning process obtained>", sub--quetions".
{{
"deccription": "<the description of the sub-
question>",
answer": <the answer to the sub-question>,
dependd: [<indices of the dependent sub sub-questions
>, ...]
}}
"answer; "[answer)"
}}
return (instruction formatter) format qquestion-questionn trajectory=tnneccoryy answer=answer)
def contract (question: str, decompose_resslle dict, independent: list, dependent: list):
instruction u*n
You are multiple choice question solver specializing in optimizing step- reasoning processes. Your task is to optimize the existing reasoning trajectory into more efficient, single self-containe question.
For the original question: (question)
Here are step-by-step reasoning process: (response}
(sub_questionl
Here explanations of key concepts:
1. self self-contained: The optimized question must solvable independently, without relying on any external information
2. efficient: The optimized question must be simpler than the original, requiring fever reasoning steps and having clearer reasoning process (these steps reduced because -problems become known conditions in the optimized question or are excluded as incorrect explorations)
solved sub
Note: Since this is multiple choice question, the optimized question must completely retain the options of the original question.
18

---

You can freely reason in your response, but please enclose the your optimized question within prrettion></uestiinnn tags uen
sub_questions au*
The following sub questiinn and their answers can serve as known conditions:
(independent)
The descriptions of the following questions can be used to form the description of the optimized problem: (dependent)
nan
answer Recompose_resull ["answer"]
for sub_e q in independent:
sub_q p"ddeene"dd", None)
sub_q in dependent:
aub_q. po..--pp("" (" None)
sub cub_questions sub-questions format (indpeendattindeeeeeeee dspendnt-(apendentt)
return instruction format (question=quettion, answer=ansver,
responae=decompose t [ response"], sub aub_question==aab_queeet qus.sistiosuuuueeciono
def judge (question: str, solutions: list): instruction
You are precise multiple choice question solver. Compare then synthesize the best ansver from multiple solutions to select the most correct option:
QUESTION: {question]
SOLUTIONS:
(solutions)
Extend your chain of thought as much as possible; the longer the chain of thought, the better.
You can freely reason in your response, even propose new reasoning to get a better answer than all solutions, but please mark the final option with kanswer>singl letter of your chosen option</ansti </ansuer> tags uen
solutions_sta ssr
for i, solution in (auleaate solutions_ f f'souution {i}: (solution)An'
prompt instruction format (quettion=question, solutions= solutions_str)
return prompt
Listing 3: Multi-hop QA
A.2 Hyperparameter Configuration
The maximum number of transitions in the Markovian reasoning chain is a key hyperparameter that controls the depth of reasoning exploration. Theoretically. longer chains enable deeper reasoning, but practical considerations require balancing performance gains with computational efficiency. Throughout our experiments, we uniformly set the maximum transition count 3, which empirically provides effective trade-off (see Section B.3 for empirical justification based on structural depth analysis).
Maximum Transition Count.
19

---

Adaptive Setting, For query-specifes optimization, the maximum transition count can be dynami- cally determined by analyzing the initial DAG structure. Since each transition ideally eliminates one layer of independent nodes (those without incoming edges), the depth of the initially decomposed DAG Go serves as a reasonable upper bound estimate for the required number of transitions. This can be computed via simple graph traversal without additional LLM invocations.
Other Hyperparameters. We use temperature T = 1.0 for all LLM sampling operations to balance exploration and determinism. For integration experiments with tree-based methods (Section 4.4), we use branches for ToT and vary the number of trees in FoT as (2, 4, 8) study scaling behavior.
A.3 Baseline Implementation Details
This subsection describes our implementation of comparisons.
bascline methods ensure fair and reproducible
A.3.1 Forest of Thoughts (FoT)
our implementation, we utilize the classical Tree Thoughts (ToT) approach as the fundamental tree structure within the Forest of Thoughts framework. while maintaining several critical mechanisms from the original FoT design, including majority voting for aggregating results across different trees and expert evaluation for assessing solution quality.
However, our implementation differs from the original FoT certain aspects accommodate broader range of question types. Specifically, we remove the early stopping criteria that terminate tree splitting when nodes cannot produce valid outputs. While this mechanism particularly effective for constrained tasks like Game-of-24 where rule-based validation is straightforward, it is less applicable to our diverse evaluation scenarios where output validity less clearly defined. Instead, we maintain tree expansion regardless of intermediate output quality, allowing the framework to explore potentially valuable paths that might initially appear suboptimal. Additionally, we omit the Input Data Augmentation technique, as analogical reasoning approaches do not demonstrate consistent effectiveness across different question domains in our experiments.
These modifications preserve the core strengths of FoT while enhancing its adaptability to wider range of reasoning tasks. Our implementation successfully reproduces the scaling curves reported in the original FoT paper and achieves superior performance across multiple benchmarks.
A.3.2 AFlow
For AFlow, we adopt the optimal workflows identified in the original work for each benchmark dataset while making necessary adaptations to our experimental setup. For mathematical reasoning tasks on MATH and GSM8K, we directly employ AFlow's proven optimal workflows. For multi-hop reasoning scenarios in LongBench, we use the workflow initially optimized for HotpotQA, as both datasets share core multi-hop reasoning characteristics. This approach ensures we leverage AFlow's strengths while maintaining consistency across similar problem types.
A.3.3 Dataset-Specific Details
For the MATH dataset, we filter out questions with non-integer or non-decimal answers to ensure consistent evaluation. We evaluate the first 1,000 cases from MATH for efficiency, while assessing the remaining benchmarks their entirety.
B Empirical Analysis and Validation
This section presents detailed empirical analyses that validate the effectiveness of our framework, including quality metrics for DAG generation, concrete examples of the decomppsition-contten process, and statistical analyses of structural properties.
20

---

B.1 DAG Generation Quality Assessment
To evaluate the quality of our two-phase transition mechanism (decomposition and contraction), we provide comprehensive quality metrics across multiple datasets. Table 2 presents three key metrics that assess different aspects of the DAG generation and state transition process.
Table 2: DAG Generation Quality Metrics Across Benchmarks
Metric
MATH
GSM8K
MBPP LongBench
Answer Equivalence Maintenance 99.2%
99.5%
99.7%
99.3%
Test-time Complexity Reduction
76.4%
82.1%
74.8%
79.2%
LLM-as-a-Judge Selection Rate
92.5%
95.8%
83.1%
91.5%
Evaluation Methodology. Both answer equivalence and test-time complexity reduction are assessed through LLM evaluation, where the evaluator LLM is provided with Q; and Qi+1 along with their exccution processes. The LLM judges answer equivalence by examining whether the reasoning trajectory's derivation goals remain consistent, and assesses complexity reduction by analyzing the trajectory length and required reasoning steps.
Metric Definitions.
Answer Equivalence Maintenance: The probability that the contracted question Q++1 maintains answer equivalence with the original question Qo. The consistently high rates (299% across all datasets) demonstrate the reliability of our transition mechanism.
Test-time Complexity Reduction: The probability that Qi+1 successfully reduces reasoning complexity compared to Q; Rates between 74%-82% indicate that most transitions achieve meaningful simplification.
The probability that Q++1 is selected (or at least not re- jected) by the LLM-as-a-judge when choosing among (Solve(Qi)) solve(G,), sooCi,,)soo(())) solve(Q++1)} High selection rates (3%-96%) confirm that the generated states provide valuable reasoning improvements.
LLM-as-a-Judeee Selection Rate:
These metries collectively demonstrate that DAG generation and contraction process reliably maintains answer equivalence while achieving meaningful complexity reduction, validating the effectiveness of our two-phase transition design.
B.2 Detailed DAG Decomposition and Contraction Examples
To provide concrete understanding of how the DAG decomposition and contraction mechanism works in practice, we present detailed step-by step-by-step examples demonstrating the complete two-phase transition process.
B.2.1 Mathematical Reasoning Example
Original Problem (Qo): There two possible triangles ABC satisfying AB 10, AC b> 10. and sin 3/5. Find the positive difference between the lengths of side BC.
Step 1: Direct Reasoning Trajectory. reasoning chain:
When solving Qo directly, the LLM generates the following
1. Given sin B 3/5, find cos B using the Pythagorean identity: cos? B + sin 2 B
2. This gives c B = (3/5)² = 1 - 9/25 16/25
3. Therefore, cos = +4/5 (two possible values)
4. Using the Law of Cosines: 12 a² ²² 2ac cos B, where a BC, c AB 10
5. For cos 4/5: 8 a² + 100 20a(4/5) a 16a 100
6. For B -4/5: 6² = a 100 20 -4/5) a 16a + 100
21

---

7. Solving these two cases yields two possible values for BC
8. The positive difference computed from these two values
Step DAG Decomposition (Qo Go). The LLM decomposes this reasoning trajectory into dependency structure:
Node 0: "Calculate cos B from sin B 3/5 using the Pythagorean identity"
Dependencies: [] (no dependencies, independent subproblem)
Result: cos = #4/5
Node 1: "Given AB 10, AC b 10, and cos B #4/5, apply the Law of Cosines to find the two possible values of BC
Dependencies: [0] (depends on the result of Node 0)
Node 2: "Calculate the positive difference between the two values of BC"
Dependencies: [1] (depends on the result of Node 1)
The DAG structure is: Node 0 Node Node 2, forming linear chain of depth 3.
Step 3: Contraction (Go + Q1). Nodes without incoming edges (Node 0) represent independent subproblems that be directly solved. After solving Node O, obtain cos +4/5. This information is incorporated into the problem statement, and nodes depending on it are reformulated:
Contracted Question (Q1): Given that cos B can be either 4/5 or -4/5, with AB 10 and AC > 10, use the Law of Cosines to find the two possible values of BC, then calculate their positive difference.
Key observations:
Q is self-contained: All necessary information (cos B values) is now explicitly stated
Q1 maintains answer equivalence with Qu: Solving Q1 yields the same final answer
Q1 has reduced test-time complexity: The trigonometric calculation is eliminated, reducing reasoning steps from approximately
The DAG depth is reduced from 3 to 2 (only Nodes 1 and 2 remain)
Step 4:
Selection. After generating the triplet (solve(Qn) solve(Go), solve(Qi)), the LLLM-a--ajjudge evaluates which provides the best answer to the original problem Qo. In this case:
LLM-as-a-Judde
solve(Qn): Direct solution with full reasoning chain
solve(Go): Solution by explicitly solving each node in the DAG
solve(Q1): Solution of the contracted problem
If Q maintains answer equivalence (which it does), solve(Q1) will provide a valid answer and is likely to be selected due its cleaner reasoning structure. If the contraction process had failed to maintain equivalence, solve(Q:) (Q1) would produce an incorrect or nonsensical answer, and the judge would select one of the other options, naturally filtering out the failed transition.
Iteration Potential. If we continue from Q1, second transition could further decompose and contract the problem, potentially separating the two Law of Cosines calculations from the difference computation. This iterative process continues until reaching an atomic state where no further meaningful decomposition is possible.
B.2.2 Key Insights from the Example
This example illustrates several important aspects of our framework:
22

---

1. Structural Guidance: The DAG explicitly captures dependencies, allowing the contraction phase identify which information can be "baked into" the problem statement (Node O's result) versus which must remain as reasoning steps (Nodes 1-2).
2. Answer Equivalence:
The contracted question Q asks for exactly the same final answer as Qu. ensuring the Markov property holds while making meaningful progress.
3. Complexity Reduction: By solving independent subproblems and incorporating their results, Q1 requires fewer reasoning steps, reducing the test-time computational burden.
4. Implicit Quality Control:
The L.LM- --a--a---udddge mechanism naturally filters failed transi- tions-if contraction produces an invalid or non-equivalent question, it won't be selected, preventing error propagation.
B.3 Analysis of Structural Diversity
To understand the structural characteristics of problems decomposed by our framework and provide empirical justification for our hyperparameter choices, we analyze the DAG structures generated from the first 1,000 questions of the MATH dataset.
B.3.1 Graph Structure and Chain Length
Problem em Count Distribution by Depth
269
250
251
200
Count
100
50
Depth
Figure 5: Distribution of solution depths across questions. Darker orange bars indicate depths that appear more frequently in the dataset.
Figures and 6 reveal clear structural patterns in the decomposed questions. The depth distribution (Figure 5) shows that most questions exhibit depths between and 4, with depth being the most common pattern. This observation provides empirical justification for our choice of maximum transition count (3) in the main experiments- the structural depth naturally aligns with the transition requirements for most problems.
Similarly, the subquestion count distribution (Figure 66) indicates that questions typically decompose into 2 to 5 subquestions, with 3-4 subquestions representing the most frequent pattern. These statistics suggest that most reasoning problems naturally decompose into a small number of manageable sub- problems, supporting our framework's 's design assumption that complex reasoning can be effectively simplified through structured decomposition.
B.3.2 Correlation Between Structural Complexity and Performance
Notably, we observed correlations between these structural metrics and solution accuracy. The scatter plots reveal two important patterns: First, as shown in Figure as the depth the solution graph increases, there is general trend of decreasing accuracy. Second, as illustrated in Figure 7 questions with more subquestions tend to show lower accuracy rates. The color intensity of the points provides additional insight darker points represent more common structural patterns in our dataset, showing
23

---

Problem Count Distribution by Subproblems
243
224
200
Count
150
132
100
75
52
50
37
2
Subproblems
Figure 6: Distribution of subquestion counts across questions. Darker green bars represent more common subquestion counts in the solutions.
Accuracy ve Number of Subproblens
Accurway
Rumber
Figure 7: Number of subquestions vs accuracy. Color intensity (green) reflects data density darker points represent more frequent patterss.
that most of our high-accuracy solutions from questions with moderate depth and subquestion counts. This suggests that more complex question structures, characterized by either greater depth or more subquestions, pose greater challenges for question-solving systems. The decline in accuracy could be attributed to error propagation through longer solution chains and the increased cognitive load required maintain consistency across more complex question structures.
NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], , [No]. or [NA]
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
24

---

Accuraay
Figure 8: Solution depth vs accuracy. Color intensity (orange) reflects data density darker points represent more frequent patterns.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers integral part of your paper submission. They visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist one of the factors in their evaluation.
While "[Yes] generally preferable to "[No] ", it perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used").
general, answering "[No] " or "[NA]" is not grounds for rejection. While the questions are phrased in binary way, acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification elaborate. All supporting evidence can appear either in the main paper the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our claims in the abstract and introduction are precise and consistent with our findings.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
25

---

Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss limitations in the Appendix ??.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approxinations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: For all the propositions and theorems presented in this paper, we provide mostly self-contained proofs in Section 3 For certain parts of the proofs, refer to well-established results from recognized papers in the literature.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
26

---

We provide detailed descriptions of our experimental setup in Section 4 We submit the code with the paper and will also release the source code to further facilitate reproducibility.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have provided the code in the supplementary file. The datasets we use are publicly available and have been accessed with the necessary permissions.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (nttps://nips.co cc/
guuides/CodeSuumisstt
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
/nips.cc/ppull http:ccccpppccccctctectccecc.clt ptuuuddeeeCodeeubbiisssooooooo.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
27

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide dedicated section in Section that details our experimental setups.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
Experimental results are tested multiple times to ensure stability and reliability,
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
If error bars are reported in tables or plots. The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
28

---

Justification: We provide comprehensive details about the compute resources used in both the experimental setup and results sections, ensuring reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't oodn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in this paper fully conforms to the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss both the potential positive and negative societal impacts of our work in Appendix ??.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologics that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
29

---

11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The paper cites the original paper that produced the models or datasets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasete has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provide the documentations alongside with the submitted code for repro- ducibility.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
30

---

The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMSs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
The LLM is only used for writing and not as part of the core methods.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM for what should should be described.
31


Reviews:
[{"review_id": "hPti8RL29c", "reviewer": "Reviewer_GRgo", "summary": "This paper introduces \"Atom of Thoughts\" (AOT), a new reasoning framework for Large Language Models that uses Markovian processes to reduce computational overhead during test-time scaling. Unlike existing methods like Chain-of-Thought that accumulate extensive historical information, AOT decomposes complex reasoning into self-contained \"atomic\" units that don't rely on previous context, making inference more efficient. The approach can be integrated with various existing reasoning methods and demonstrates consistent performance improvements as computational budgets increase.", "questions": "Does the cost in Figure 4 include the LLM-as-judge and the construction and transition of AoT?", "limitations": "Authors have discussed their limitations and social impact in the paper", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* Different from previous decompositions, this paper defines a memoryless state in a Markov process, where each state only relies on the one step before. The decomposition requires that each sub-question preserve answer equivalence with the original question. AoT uses a two-phase transition to formulate such a memoryless Markov process, which first creates a DAG and then transfers the DAG to \nanswer an equivalent independent question. To ensure the equivalence, it uses LLM-as-a-judge to evaluate the state transition. \n* The paper provides comprehensive experiments to demonstrate the effectiveness of AoT in different tasks and settings. Experimental results on various tasks (math, code, and QA) show that AoT can improve the model performance in different domains. It also includes the integration of AoT to other reasoning frameworks and the investigation of the scaling law from different aspects. \n\n\nWeaknesses: \n* The motivation is not very clear to me. The construction of memoryless state Qi is based on the DAG. If there is a correct DAG decomposition of the original problem Q0, why not solve the problem directly following the dependencies in this DAG? Since each node in this DAG is an individual thought or sub-question, it should be easier to solve.  However, AoT chooses to convert the DAG to a new answer-equivalence question and solve it, which may lead to unnecessary cost by recreating a similar graph structure again (as in ToT and GoT).\n* The performance improvement over the baselines is not significant on MATH, GSM8k, MBPP, and AIME in Table 1. \n* The reliability of the answer-equivalence of the state transition depends on LLM-as-a-Judge. In other words, the LLM-based judge is used to check the correctness of the new conditions (independent sub-problems or thoughts). Therefore, the baselines such as FoT and ToT should also use the same LLM-as-a-Judge as the reward function. \n\nOthers:  \n* In Table 1,  AFlow's performance based on DeepSeek-V3 on GSM8k is the highest and should be bolded. \n* The font of legends in Figures 3 and 4 is too small.", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for your insightful comments and suggestions. We provide detailed responses point by point below. We hope that our clarifications, additional experiments, and responses can address your concerns and provide helpful insights for your evaluation.\n\n> ### Further Clarification on LLM-as-a-Judge\n\nRegarding your mention in the strengths about \"using LLM-as-a-judge to evaluate the answer equivalence of state transitions,\" we would like to clarify that our LLM-as-a-judge design ensures post-transition equivalence through its ingenious design, where ensuring answer equivalence is merely an additional benefit rather than the primary judgment criterion. \n\nIn practice, our LLM-as-a-judge selects the best answer from the triplet $(Q\\_i, G\\_i, Q\\_{i+1})$ containing solving information as the evaluation standard. This design **does not require additional reasoning costs** to judge answer equivalence, because $Q\\_{i+1}$ that fails to satisfy answer equivalence cannot possibly be selected under this evaluation mechanism. This represents an implicit equivalence guarantee mechanism.\n\n> ### W1: Clarification on Motivation\n\nThank you for pointing out that the motivation needs clearer articulation. We want to clarify that the nodes in the DAG are actually in a solved state, so \"solve the problem directly following the dependencies in this DAG\" is indeed the actual situation, because structural relationships cannot be separated from the solving trajectory.\n\nFor example, when we solve the problem in Figure 1: \"There are two possible triangles ABC satisfying AB \\= 10, AC \\= b \\> 10, and sin B \\= 3/5. Find the positive difference between the lengths of side BC.\", we cannot generate the second sub-question as \"Given cosB=answer of subquestion1, solve for the positive difference between the lengths of side BC.\", because this neither saves tokens nor follows common paradigms in natural language reasoning, and it would also lose branching cases, since without solving, the fact that cosB has two possible values here would not be obvious.\n\nRegarding the cost of generating graph structures, we must emphasize that our LLM-as-a-judge design ensures that if additional costs are incurred to continue generating graphs, it indicates that the original graph fails to achieve favorable outcomes in the LLM-as-a-judge evaluation. This implies that the LLM's reasoning process deems such cost expenditure necessary to yield direct performance improvements, making it both essential and beneficial. \n\nFurthermore, due to the test-time complexity reduction requirement during the contraction phase, **AoT ensures at least a non-increasing trend in the complexity of graph structures produced in subsequent transitions**. The increased number of transitions arises from the need for further reasoning, but it does not lead to a linear increase in costs by \"recreating a similar graph structure again.\" Instead, it results in a simpler graph to rectify the suboptimal quality of previous graphs, as the contraction process removes nodes without incoming edges or subsequent dependencies.\n\n> ### W2: Regarding Performance Improvements\n\nRegarding the issue of insignificant performance improvements, we clarify that our main experiments (Table 1) utilize the lightest setting: single Markov chain exploration, which is our core design, without resampling nodes and chains as seen in ToT and FoT's tree search approaches. In Section 4.4's scaling analysis, combining reflection and tree search mechanisms (validated in prior works) with Markov chain exploration results in much more significant gains (Figure 4). We have excluded these results from Table 1 to highlight Markov chain exploration as our fundamental contribution, while acknowledging reflection and tree structures as established prior works for further scaling. To address your concerns, we conducted tests with \"ToT + Markov chain + Reflective Refinement\" (denoted as AoT\\* in the table below) on the mentioned datasets, with the results presented as follows:\n\n**Table: Extended Experiments with Test-Time Scaling Integration**\n\n| Dataset | Method | Accuracy (%) | Cost (USD) | Dataset | Method | Accuracy (%) | Cost (USD) |\n| :---- | :---- | :---- | :---- | :---- | :---- | :---- | :---- |\n| MATH | ToT | 82.0 | 0.351 | AIME | ToT | 78.0 | 0.029 |\n| MATH | FoT (n=8) | 81.7 | 7.283 | AIME | FoT (n=8) | 79.0 | 0.597 |\n| MATH | AoT\\* | **84.9** | 11.650 | AIME | AoT\\*  | **81.2** | 1.853 |\n| GSM8K | ToT | 91.8 | 0.126 | MBPP | ToT | 73.5 | 0.089 |\n| GSM8K | FoT (n=8) | 94.2 | 2.622 | MBPP | FoT (n=8) | 74.8 | 1.845 |\n| GSM8K | AoT\\* | **95.1** | 5.850 | MBPP | AoT\\*  | **79.1** | 2.650 |\n\n> ### W3: Regarding LLM-as-a-Judge for Baseline Methods\n\nWhen implementing same-layer node evaluation for ToT and FoT, **we used LLM-as-a-judge with prompt designs aligned as closely as possible with AoT**. Specifically, all methods follow similar principles in LLM-as-a-judge prompt design: selecting the optimal among multiple solving trajectories. For ToT and FoT, these solutions contain reasoning trajectories for the original problem; for AoT, the selection is among triplets $(Q\\_i, G\\_i, Q\\_{i+1})$ generated from a single state transition. This ensures fairness in comparison.\n\n> ### Q1: Regarding Cost Calculation in Figure 4\n\nRegarding the question about \"whether the costs in Figure 4 include LLM-as-a-judge and AoT's construction and transformation,\" we clearly answer: **Yes, completely included**.\n\nTo ensure fairness in experimental comparison, we include the complete reasoning process of all methods in the cost calculation:\n\n- **ToT and FoT**: Include costs of all LLM calls for node generation, node evaluation, etc.  \n- **AoT**: Similarly includes all costs for DAG generation, two-phase transition, and LLM-as-a-judge selection among triplets $(Q\\_i, G\\_i, Q\\_{i+1})$\n\nThis comprehensive cost calculation ensures our comparison results truly reflect the actual computational overhead of each method, demonstrating the rigor and fairness of our experimental design.\n\n> ### Others: Additional Issues\n\nThank you for pointing out that the AFlow results based on DeepSeek-V3 on GSM8K data in Table 1 should be bolded. After our review, this occurs in the MATH dataset, and we will make the corresponding correction in the revision. Regarding the issue of overly small font sizes in the legends of Figures 3 and 4, we will also increase the font sizes to ensure clear readability."}, {"review_id": "1P5ssSDW1M", "reviewer": "Reviewer_VGGy", "summary": "This paper proposes a prompting framework, which interatively instructs an LLM to (1) reason over a question, (2) decompose its reasoning path into sub-thoughts and offers their dependency structure, and (3) generate the simpler question by reflecting on the generated structure.", "questions": "please refer to **Weakness** section.", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "### **Strengths**\n\nThis paper discusses a paradigm of problem solving in LLM, which is to progressively simplify a complex problem as a whole step by step. The core concept makes a lot sense to me, and seems to be rarely addressed in exsiting literature. The core concepts, practical experiences, and some technical approaches presented in this paper, may offer some insights to the research community engaged in tasks that involving similar problem-solving frameworks.\n\n### **Weaknesses**\n\n#### **W1: Significant Presentation Issues**\n\nThe overall organization and some detailed presentations of this paper makes it difficult to follow. Just to list a few points:\n\n-   Figures\n    - Too small font size for all figures.\n    - Confusing presentation for Figure 1 and 2. I failed to grasp the x-axis meaning in Figure 1 and the logical flow in Figure 2 until comprehending the core methodology.\n-   Method\n    - The intro section fails to outline the general framework of the proposed method, instead listing unexplained concepts.\n    - The basic and overall instruction detailed in Appendix C should be given in Section 3.1. I fully understand and respect the author(s)' efforts to keep the mathematical rigor, but I think giving certain intuition is not harmful.\n-    Organization\n     - Section 3.2 is confusing. It contains both addtional tricks and analysis, some of which don't fall under the title \"Emerged Atomic Reasoning\".\n     - So is Section 4.4.\n\n#### **W2: Unsupported Claims**\n\nThis paper gives unsupported claims. For example:\n\n> These structured explorations reveal a statistically supported phenomenon: deeper reasoning states tend to converge into irreducible forms, maintaining a stable and relatively low reasoning token count, from which the original problem’s answer can be directly inferred with high execution stability.\n\nThe \"structured explorations\" and statistics are missing.\n\n> Due to AOT ’s design and termination mechanism, longer chain lengths increase the performance ceiling without linearly increasing costs.\n\nI don't think the existing results can support \"increase the performance ceiling\".\n\n> In practice, this can also be query-specific based on the current problem; that is, we can add an additional LLM invocation to calculate the depth of the DAG as an estimate of a theoretically optimal maximum number of transitions.\n\nThe practical experiment is missing. And it's debatable whether the LLM estimation can be viewed as \"theoretically optimal\".\n\n#### **W3: Missing Important Analytical Details**\n\n- One of the paper's main contribution is the design to instruct LLMs converting a reasoning path into a DAG. However, the quality of DAG generated is not discuessed, making the result not interpretable and less reliable.\n- the choice of transition hyperparameters as 3 is not supported. According to Appendix E, it seems that a larger number may be a better choice.\n- The proposed method uses LLM-as-a-Judge as a important trick, but the statistics of it is missing. For example, how often does the judge interupt the process?", "was_revised": true, "final_justification": "Raise rating from 2 to 3 because:\n- The responses are very diligent and informative, and the new experiments results reveal more fine-grained intermediate statistics about LLM judge processes.\n\nStill a bordeline reject because:\n- W1: Not acceptable presentation from my perspective.\n- W2: Misleading- or over-claiming.\n- W3: Still a little questionable implementation details and hyperparameter selection, might compromising reliability.", "rebuttal": "We would like to thank you for your insightful comments and suggestions. We provide detailed responses point by point below. We hope that our clarifications, additional experiments, and responses can address your concerns and provide helpful insights for your evaluation.\n\n> ## W1: Significant Presentation Issues\n\nWe acknowledge the presentation concerns and will implement improvements to enhance readability:\n\n### Figures\n\n- **Font size**: We will increase font sizes across all figures to ensure clear readability  \n- **Figure 1 and 2 clarity**: We acknowledge that the methodological differences leading to Figure 1's performance patterns and the meaning of various arrows in Figure 2's process flow may require deeper engagement with the paper content to be fully appreciated. We will enhance these figures by incorporating concrete examples that demonstrate how the DAG decomposition process works in practice and providing more detailed captions.\n\n### Method\n\n- **Introduction framework overview**: Our introduction systematically introduces key concepts with clear explanations: the memoryless property of Markov processes, the Markovian reasoning process, the two-phase state transition mechanism with its decomposition and contraction stages. The framework is outlined through the logical progression from problem identification (historical dependency issues) to solution design (Markovian reasoning process). We would much appreciate it if the reviewer could specify which particular concepts led you to consider them unexplained, as this would help us make the paper clearer and better serve readers  \n- **Basic section and Appendix C instructions**: While maintaining paper length constraints, we will incorporate key prompt descriptions from Appendix C into Section 3.1 to balance mathematical rigor with reader accessibility\n\n### Organization\n\n- **Section 3.2 structure**: The section actually follows a deliberate progression: (1) **Termination Strategy** - establishing robustness for safe scaling, (2) **Modular Integration** - demonstrating how Markov states enable efficient integration with method, and (3) **Atomic Reasoning** - showing how these mechanisms naturally lead to minimal, stable reasoning structures. \n\n- **Section 4.4 clarity**: Section 4.4 provides systematic empirical validation of our test-time scaling framework: Section 4.4 systematically validates our test-time scaling framework through integrating Markov chain structure assumptions with tree search and reflection verification mechanisms, thereby expanding the state space. This section offers critical empirical evidence supporting the theoretical framework established in Section 3.2.\n\n> ## W2: Unsupported Claims\n\nWe address each identified claim with additional evidence:\n\n### On \"Structured Explorations\" and Statistical Evidence\n\nWe appreciate the opportunity to elaborate on this point. As demonstrated in Section 4.4, the experiments directly reflect the benefit of structured exploration. By combining classical mechanisms such as Markov chain reasoning, tree search, and reflection, our method exhibits progressively improved performance. More importantly, the required number of reasoning steps gradually converges to a lower ratio, indicating improved efficiency. The stability of execution arises from a reduction in reasoning complexity, which effectively narrows the solution space and enhances robustness.\n\n### On \"Performance Ceiling\" Claims\n\nWe thank the reviewer for raising this important point. We acknowledge that our statement regarding the \"performance ceiling\" requires clarification, and we welcome the chance to provide supporting evidence.\n\nBy \"performance ceiling,\" we refer to the AoT's potential to achieve higher performance on complex problems when allowed longer maximum chain lengths. Our termination mechanism ensures that the actual computational cost remains low for simpler problems, as chains automatically terminate early when no further improvement is detected.\n\nThe key contribution lies in our quality-aware termination strategy: it evaluates each transition and halts the chain once no further progress is observed. This design allows us to raise the maximum chain length—thus increasing the ceiling of what our system can achieve on harder tasks—without significantly raising the average cost across tasks.\n\nOur experimental results in Figure 3 and Figure 4 support this claim: performance maintains a steady upward trend as the number of iterations increases, demonstrating that longer chains can achieve higher performance levels when necessary. Specifically, Figure 4, by integrating tree search and reflection, further explores the potential Markov chain space, significantly surpassing the performance ceiling of methods originally based on ToT and reflection. For instance, on the AIME dataset, our method, under the highest cost setting, achieves a remarkable 94.3% accuracy, substantially outperforming FoT with 8 trees (81.8%), which highlights the effectiveness of our approach in pushing performance boundaries.\n\n### On \"Theoretically Optimal\" Estimation\n\nWe would like to clarify a possible misunderstanding regarding our description of \"theoretical optimality.\" The LLM is only responsible for converting the initial reasoning structure into a JSON-formatted DAG. The estimation of DAG depth for the initial graph $G_0$ is performed entirely by a rule-based algorithm—not the LLM. Therefore, the depth does not reflect the LLM’s real-time estimation but rather an upper bound or idealized measure of its reasoning potential.\n\nTheoretically, in an idealized setting, each transition should remove one layer of nodes with no incoming edges, reducing the DAG depth by one. However, in practice, individual transitions may fail to eliminate entire layers due to insufficient complexity reduction. As a result, the initial DAG depth often underestimates the number of transitions actually needed to reach an irreducible state.\n\nWe will clarify this distinction in the revised manuscript and provide further explanation to avoid potential confusion.\n\n> ## W3: Missing Important Analytical Details\n\nWe agree on the importance of DAG analysis details and will supplement relevant experiments:\n\n### DAG Generation Quality\n\nA core component of our decomposition phase is instructing LLMs to convert reasoning paths into DAGs. We recognize that further discussion on DAG quality would enhance interpretability. Therefore, we provide comprehensive DAG quality metrics across multiple dimensions:\n\n**Table: DAG Quality Assessment Metrics**\n\n| Metric | MATH | GSM8K | MBPP | LongBench |\n| :---- | :---- | :---- | :---- | :---- |\n| Answer Equivalence Maintenance | 99.2% | 99.5% | 99.7% | 99.3% |\n| Test-time Complexity Reduction | 76.4% | 82.1% | 74.8% | 79.2% |\n| LLM-as-a-Judge Selection Rate | 92.5% | 95.8% | 83.1% | 91.5% |\n\nThese metrics demonstrate: (1) **Answer Equivalence Maintenance**: the probability that $Q\\_{i+1}$ maintains equivalence with the original $Q\\_{i}$; (2) **Test-time Complexity Reduction**: the probability that $Q\\_{i+1}$ successfully reduces reasoning complexity; (3) **LLM-as-a-Judge Selection Rate**: the probability that $Q\\_{i+1}$ is at least not providing a worse answer.\n\n**Evaluation Methodology**: Both answer equivalence and test-time reduction are assessed through LLM evaluation, where the evaluator LLM is provided with the $Q_i$ and $Q_{i+1}$ along with their execution processes. The LLM can intuitively judge answer equivalence from the reasoning trajectory's derivation goals and assess complexity reduction from the trajectory length and reasoning steps required.\n\n### Transition Hyperparameter Choice and Depth Analysis\n\nTo validate our choice of maximum transition count, we conducted a comprehensive depth analysis using the MATH dataset. By setting the maximum depth to 10 and extracting reasoning results at each Markov chain depth, we effectively simulated experiments with different maximum transition counts (1 through 10\\) while eliminating random sampling variance:\n\n| Maximum Transition Count | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |\n| :---- | :---- | :---- | :---- | :---- | :---- | :---- | :---- | :---- | :---- | :---- |\n| Accuracy (%) | 82.6 | 83.0 | 83.6 | 83.7 | 83.6 | 83.6 | 83.5 | 83.6 | 83.6 | 83.6 |\n\nThe results reveal a clear pattern: **performance improvements plateau after 3 transitions, with negligible gains beyond this point.** This empirical evidence strongly supports our default setting of 3 maximum transitions, which optimally balances exploration effectiveness with computational efficiency.\n\nRegarding the connection with Appendix E, we appreciate the opportunity to clarify. The purpose of Appendix E is to present statistical results to \"understand the structural characteristics of decomposed questions.\" The detailed analysis presented there examines DAG structures generated in the initial decomposition step, focusing on structural properties rather than performance outcomes.\n\nIn practice, our Markov chain exploration employs an adaptive termination mechanism that exits early when quality improvements cease to materialize. This means the system rarely explores to the theoretical maximum depth, as it intelligently conserves computational resources once diminishing returns are detected. This design philosophy ensures both efficiency and solution quality, making the choice of 3 transitions both theoretically sound and practically optimal.\n\n### LLM-as-a-Judge Usage Statistics\n\nWe agree this is important. As shown in the DAG Quality Assessment Metrics table above, the LLM-as-a-Judge Selection Rates are **consistently high across datasets (92.5% on MATH, 95.8% on GSM8K, 83.1% on MBPP, and 91.5% on LongBench)**, demonstrating effective quality control and helping with cost control. We will add these statistics (interruption frequency distribution and performance impact) to make the method more transparent."}, {"review_id": "Ejq57Vqg5e", "reviewer": "Reviewer_cbHf", "summary": "This paper presents the \"Atomic of Thought\" (AoT), a new way for large language models (LLMs) to reason that intends to improve testing scalability by reducing the need for historical context.  AoT models the reasoning process as a Markov chain, which is different from other methods like Chain-of-Thought and Tree-of-Thought. Each \"state\" in the chain is a self-contained, equivalent restatement of the original problem, with reduced complexity. Through a large number of experiments on mathematical, coding, and question-answering benchmarks, AoT consistently demonstrates superior performance compared to existing methods. Moreover, this paper has a unique finding, the \"emergent\" property of atomic reasoning, where complex problems are progressively decomposed into indivisible, self-contained units.", "questions": "1. The author notes that the chain's memoryless property makes it vulnerable to poor transitions. What is the failure rate of these transitions, and what are the predominant modes of failure?\n2. AoT introduces new computational costs, including calls for decomposition, contraction, and quality-aware termination using an LLM-as-a-judge. Could you provide more details on the computational cost?\n3. Could you discuss what degree the AoT framework demonstrates sensitivity to the specific prompts utilized for deconstruction, contraction, and evaluation?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- Modeling reasoning as a Markov process of answer-equivalent states is an effective approach. This solves the important issue of context explosion and redundant computation in test-time scaling, which is an important issue for complex LLM inference. \n  -The suggested AoT framework gives a reasonable and useful answer. A probabilistic formulation and a real two-phase (Decomposition-Contraction) implementation define the methodology. The extensive experimental evaluation well supports the AoT's effectiveness, includes a wide range of tasks, several state-of-the-art LLMs, and a full set of strong baselines. The submission's claims are also backed up by the inclusion of detailed ablation studies and scaling analyses, such as integration with ToT/FoT.\n- This submission is generally well-organized. \n\n**Weaknesses**\n\n- This submission makes strong claims, such as that \"answer-equivalence\" will be kept, but it doesn't explain how this will be checked or enforced.\n- This submission says that \"atomic reasoning\" is a new property that was found when the process was scaled up. However, calling it the discovery of a \"latent granularity\" might be too much. Another way to look at it is that the system is reaching a logical endpoint, beyond which breaking it down further is not useful or possible for the given problem structure. \n- AoT seems to work best when the prompts for the decompose and contract functions are well thought out. Giving the prompts is good for making sure the results can be repeated, but it also raises problems about whether the framework is sensitive to how the prompts are worded. Further discussion is needed on how well AoT can handle changes to these master prompts to improve the work. It would also be interesting to see if it could be added to the prompt tuning framework, just like [Dspy](https://dspy.ai/).", "was_revised": true, "final_justification": "This submission focuses on trendy problems with extensive experiments. During the discussion period, the author answered my problem in detailed responses. Thus, I keep my score of 4 and am inclined to accept this submission, as it could bring insights for this community.", "rebuttal": "We would like to thank you for your insightful comments and suggestions. We provide detailed responses point by point below. We hope that our clarifications, additional experiments, and responses can address your concerns and provide helpful insights for your evaluation. \n\n> ### W1: Enforcement Mechanism for Answer Equivalence\n\nThank you for pointing out this critical issue. We acknowledge that the paper's description of how to check and enforce answer equivalence could be clearer.\n\nOur framework ensures answer equivalence through a sophisticated mechanism: as described in Section 3.2, after each Markov transition, we employ LLM-as-a-judge to select the best answer to current original questio $Q\\_i$ from the triplet $(Q\\_i, G\\_i, Q\\_{i+1})$. The key insight of this mechanism is: **we do not need to explicitly check answer equivalence, because $Q\\_{i+1}$ that fails to satisfy answer equivalence is almost impossible to be selected as the best answer**.\n\nSpecifically, the task of LLM-as-a-judge is to select the optimal solution for the original question $Q\\_i$. If the contraction process destroys answer equivalence, $Q\\_{i+1}$ will be unable to provide a valid answer for $Q\\_i$ and thus will not be selected. This selection mechanism acts as a natural quality filter, implicitly enforcing the answer equivalence constraint.\n\nExperimental data supports the effectiveness of this mechanism: our comprehensive DAG quality metrics show that Answer Equivalence Maintenance rates are consistently high across all datasets (99.2% on MATH, 99.5% on GSM8K, 99.7% on MBPP, and 99.3% on LongBench), with LLM-as-a-Judge Selection Rates of 92.5%, 95.8%, 83.1%, and 91.5% respectively. This demonstrates that our mechanism is not only theoretically sound but also highly reliable in practice.\n\n**Evaluation Methodology**: Both answer equivalence and test-time reduction are assessed through LLM evaluation, where the evaluator LLM is provided with the $Q_i$ and $Q_{i+1}$ along with their execution processes. The LLM can intuitively judge answer equivalence from the reasoning trajectory's derivation goals and assess complexity reduction from the trajectory length and reasoning steps required.\n\nWe will more clearly articulate this implicit enforcement mechanism in the revision, emphasizing how it naturally maintains answer equivalence through the selection process without requiring additional explicit checking steps.\n\n> ### W2: \"Atomic Reasoning\" as an Emergent Property\n\nWe greatly appreciate the reviewer's nuanced perspective. After deep reflection, we recognize that describing atomic reasoning as reaching a \"logical endpoint\" rather than discovering \"underlying granularity\" is indeed more accurate. The phenomenon we observe is that through continuously increasing test-time reasoning, the Markov chain gradually approaches an irreducible state where problems are sufficiently simple and execution results are sufficiently stable that further decomposition lacks meaning. However, the specific depth of this convergence is likely closely related to the LLM's reasoning capabilities rather than being entirely determined by the intrinsic properties of the problem itself. Therefore, our method is better viewed as a means of observing and exploring the reasoning process rather than revealing inherently existing hidden structures. We will revise our description accordingly, emphasizing that this represents a convergence point under given LLM capabilities and clearly noting this limitation.\n\n> ### W3: Prompt Sensitivity and Robustness\n\nThank you for this insightful suggestion. To assess the sensitivity of AoT to prompt variations, we conducted additional experiments evaluating its robustness under different prompting strategies.\n\nWe chose to use **OPRO** over DSPy for prompt optimization due to implementation compatibility: AoT's architecture relies on custom LLM call chains that DSPy's current framework does not natively support. OPRO's lightweight design proved better suited for our purposes, while still yielding effective prompt refinement. Our OPRO configuration uses a maximum of 10 optimization steps, with 8 prompt candidates sampled at each step. We will include these robustness experiments in the revised version and expand the discussion around the integration of OPRO with AoT.\n\n**Table: AoT Performance Under Different Prompt Strategies**\n\n| Dataset | Default Prompt | OPRO-Optimized Prompt |\n| :---- | :---- | :---- |\n| MATH | 78.3% | 79.2% |\n| LongBench | 68.5% | 68.8% |\n| MBPP | 72.4% | 73.3% |\n| MATH\\* | 84.9% | 84.8% |\n| LongBench\\* | 73.5% | 73.3% |\n| MBPP\\* | 79.1% | 79.2% |\n\nThese results demonstrate that AoT is **highly robust to prompt variations**. With OPRO-based prompt optimization, performance improved by an average of 0.7%, confirming that AoT’s prompts—based on simple, direct task descriptions—are already near-optimal. This robustness stems from our deliberate avoidance of brittle or overly engineered templates.\n\nIt is also worth noting that while automatic prompt tuning techniques like OPRO or DSPy can help discover effective prompts on in-distribution data, they typically require significant token budgets for search and optimization. In contrast, AoT's design favors **efficient integration with classical reasoning frameworks** over heavy reliance on prompt tuning. From an efficiency perspective, directly scaling AoT via principled integration (e.g., with tree searching or reflection mechanisms) offers a more practical and cost-effective path.\n\nImportantly, when we apply the same test-time scaling integration setting from Section 4.4—which combines **ToT + Markov Chain + Reflective Refinement**—prompt sensitivity becomes virtually negligible. The datasets marked with \\* represent performance under this exact same experimental configuration as presented in Section 4.4, but now evaluated with different prompt strategies. In these settings, the performance difference between default and OPRO-optimized prompts drops to ≤0.1%, indicating that the multi-step reasoning and refinement mechanisms effectively absorb prompt-level variations. This stark contrast with the 0.7% gap in the base setting underscores how AoT’s robustness further improves under advanced reasoning configurations, reducing the need for prompt optimization altogether.\n\n> ### Q1: Regarding Transition Failure Rates and Failure Modes\n\nThank you for your insightful comment. You are correct that when adapting classical Markov chain theory to general reasoning scenarios, the memoryless property presents a fundamental challenge: poor transitions can lead to significant degradation as the chain discards previous information and cannot self-correct in subsequent steps. This theoretical limitation has historically hindered the application of Markovian frameworks to complex reasoning tasks. However, our AoT design elegantly addresses this challenge through both theoretical and practical safeguards:\n\n1. **Theoretical Foundation:** Through logical derivation of Markov chains for general reasoning scenarios, we propose **answer equivalence** as an invariant property across states, coupled with **test-time reduction** as a requirement to drive reasoning progress. This theoretical insight enables the implementation of concise and effective prompts, reducing the likelihood of destructive LLM transitions while maintaining the efficiency and stability of our reasoning framework.  \n     \n2. **Practical Implementation:** To enforce this constraint, we introduce the termination strategy (as detailed in W1), which serves as a strict gatekeeper, ensuring that only transitions maintaining answer equivalence are allowed.  \n     \n3. **Empirical Evidence:** Our experimental results demonstrate the effectiveness of these safeguards, with failure rates consistently below 1% across various datasets:\n\n| Dataset | Failure Rate |\n| :---- | :---- |\n| MATH | 0.8% |\n| GSM8K | 0.5% |\n| MBPP | 0.3% |\n| LongBench | 0.7% |\n\nThese results underscore the robustness of our approach in maintaining answer equivalence, mitigating the risk of catastrophic failure even in memoryless chains.\n\n> ### Q2: Regarding Computational Cost Details\n\nThank you for asking about the detailed computational costs. Each AoT transition involves three LLM calls with the following cost distribution (using MATH dataset as an example):\n\n| Component | Cost Proportion |\n| :---- | :---- |\n| Contraction $(G\\_i → Q\\_{i+1})$ | 27% |\n| Decomposition $(Q\\_i → G\\_i)$ | 32% |\n| LLM-as-a-Judge Selection | 41% |\n| **Total** | **100%** |\n\nThe LLM-as-a-judge represents the most expensive component, while contraction is the most cost-efficient step in each transition.\n\n> ### Q3: Regarding Prompt Sensitivity\n\nAs detailed in section W3, our experiments demonstrate that AoT has strong robustness to prompt variations. When comparing default prompts with OPRO-optimized prompts, AoT shows minimal performance differences (≤0.1% in scaled-up settings), indicating that our simple, direct task descriptions are already near-optimal and do not require complex engineered templates.\n\nWe are certainly willing to discuss the differences in prompt sensitivity for execution, decomposition, contraction, and evaluation components. Since execution and evaluation receive direct feedback through comparison with ground truth, prompt tuning in these steps results in observable performance improvements. We attempted to optimize prompts for decomposition and contraction using indirect feedback, but performance significantly declines when generated prompts deviate from fundamental requirements such as answer equivalence. Additionally, at this stage, automatic prompt tuning mainly adjusts superficial terms like \"systematically\" and finds it difficult to optimize core design principles."}, {"review_id": "9eZMeirOVb", "reviewer": "Reviewer_jQ8z", "summary": "The paper proposes Atom of Thoughts (AoT), a reasoning framework that leverages Markovian transitions to minimize historical dependencies during inference. There are two key components of the AoT framework: (1) two-phase transition where the system first decomposes the problem before solving it; (2) DAG-guided transition: when transforming the temporary DAG structure into the next Markov state, the method prunes nodes without incoming edges and reformulates it into an answer-equivalent independent question. Experimental results show that AoT consistently outperforms baselines as computational budgets increase, which provides a potential path of inference-time scaling.", "questions": "Besides questions raised in \"Weaknesses\", I have the following suggestion:\n\nWhile Figure 1 (b) is helpful for understanding the proposed method, it would be great if the paper could include a step-by-step example in the Appendix to help readers go through the process of DAG construction and reformation. As a reader, I found the process is conceptually intuitive but still somewhat complicated to apply in LLM reasoning domains.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The proposed method provides a novel approach for leveraging the structure information for reasoning task. While language models simplify many problems into next token prediction, it is interesting to see adding back the structure could help language models to reason and it also has the good property of modular integration as discussed in the paper.\n2. The baseline comparison is comprehensive. Figure 3 is also informative as it shows the potential of AoT for inference-time scaling. Besides the aggregated performance, I am wondering where there exists patterns of what we could get out of scaling with AoT. For example, after giving the framework more compute, what types of problems get resolved and why other methods fail to resolve them as the compute scales.\n\nWeaknesses:\n1. It is unclear how the two-phase transition is exactly executed. According to my understanding, it is using language model to generate the DAG. As this step is complicated, I am wondering what the accuracy is for this step.\n2. One assumption of AoT is that for each question $Q_0$, we can construct a sequence of subquestions that have equivalent answers but monotonically reduces in complexity. As the datasets experimented in this paper all have a short gold answer, I am wondering whether the method could be generalized to other reasoning scenarios, like writing complicated code, or writing mathematical proofs.", "was_revised": true, "final_justification": "I keep the score unchanged because while the author response is helpful for understanding the paper better, I believe my original score has already leaned towards acceptance and reflects my judgment of the paper's contribution.", "rebuttal": "We would like to thank you for your insightful comments and suggestions. We provide detailed responses point by point below. We hope that our clarifications, additional experiments, and responses can address your concerns and provide helpful insights for your evaluation.\n\n> ### S1: Novel Structured Approach and Modular Integration\n\nThank you for highlighting the novelty of our approach in leveraging structural information to enhance LLM reasoning, including its modular integration properties. We fully agree and would like to elaborate on the multi-factorial aspects that contribute to AoT's performance improvements through its Markov chain formulation:\n\n- **Multi-Perspective Synthesis via Triplets**: Each transition generates a triplet (Q_i, G_i, Q_{i+1}), providing three complementary perspectives on the problem. This is more efficient than methods like ToT or FoT, which accumulate information through repeated comparisons and branching, potentially leading to computational overhead without guaranteed progress.\n\n- **Expanded Modeling Space for Reasoning Trajectories**: Unlike standard CoT or simple decomposition methods that follow linear or fixed paths, AoT's Markov chain framework offers a larger, more flexible space for modeling reasoning trajectories. This enables adaptive exploration through multiple state transitions, allowing the system to self-correct and refine solutions dynamically while maintaining structural integrity.\n\nThese factors lead to enhanced effects in statistical patterns, while analysis of specific cases may not well reflect the essence. However, we have indeed observed some particularly special situations, such as in certain multi-hop problems where the gap between decomposition and direct solving is very large. The granularity of the solving trajectory directly leads to deviations in understanding, and the multi-perspective transition process has a significant advantage in such problems.\n\n> ### W1: Clarity of Two-Phase Transition Execution\n\n### 1. Decomposition Phase $(Q_i \\rightarrow G_i)$\n\nThe decomposition is completed through a **single LLM call**. We simply prompt the LLM to:\n- Identify reasoning units (subproblems or thoughts) as DAG nodes\n- Record dependencies between units as directed edges\n- No format constraints - the LLM freely analyzes the reasoning structure\n\n### 2. Contraction Phase $(G_i \\rightarrow Q_{i+1})$\n\nThe contraction is also a **single LLM call**, where the LLM:\n- Analyses the structural information from $G_i$\n- Generates a new problem $Q_{i+1}$ that preserves answer equivalence while reducing complexity\n\n### 3. Quality Assurance\n\nAs described in Section 3.2, we use LLM-as-a-judge to select the best answer from $Q_i$, $G_i$, and $Q_{i+1}$. This mechanism naturally filters out any failed transitions - if decomposition or contraction fails, $Q_{i+1}$ won't be selected as the final reasoning basis.\n\n### Accuracy Metrics for DAG Generation\n\nTo evaluate the quality of the two-phase transition process, we provide comprehensive experimental metrics across multiple datasets:\n\n**Table: DAG Quality Assessment Metrics**\n\n| Metric                          | MATH  | GSM8K | MBPP  | AIME  |\n|---------------------------------|-------|-------|-------|-------|\n| Answer Equivalence Maintenance  | 99.2% | 99.5% | 99.7% | 99.3% |\n| Test-time Complexity Reduction  | 76.4% | 82.1% | 74.8% | 79.2% |\n| LLM-as-a-Judge Selection Rate   | 92.5% | 95.8% | 83.1% | 91.5% |\n\nThese metrics demonstrate: \n\n(1) **Answer Equivalence Maintenance**: the probability that $Q_{i+1}$ maintains equivalence with the original $Q_i$; \n\n(2) **Test-time Complexity Reduction**: the probability that $Q_{i+1}$ successfully reduces reasoning complexity;\n\n(3) **LLM-as-a-Judge Selection Rate**: the probability that $Q_{i+1}$ is selected as providing at least equivalent quality reasoning.\n\n**Evaluation Methodology**: Both answer equivalence and test-time reduction are assessed through LLM evaluation, where the evaluator LLM is provided with the $Q_i$ and $Q_{i+1}$ along with their execution processes. The LLM can intuitively judge answer equivalence from the reasoning trajectory's derivation goals and assess complexity reduction from the trajectory length and reasoning steps required.\n\nThe consistently high answer equivalence maintenance rates (>99% across all datasets) directly address your concern about DAG generation accuracy, demonstrating that LLMs can effectively execute structured DAG decomposition and contraction with remarkable reliability and consistency.\n\n> ### W2: Generalizability to Complex Reasoning Scenarios\n\nThank you for this insightful question about generalizability to complex reasoning scenarios like complicated code writing and mathematical proofs. We provide both theoretical analysis and preliminary evidence for broader applicability:\n\n**Regarding Complex Code Generation:** We note that our evaluation already includes LiveCodeBench, which represents a challenging and complex coding benchmark that tests real-world programming scenarios. Our results on LiveCodeBench (Table 1) demonstrate that AoT can effectively handle complex programming tasks through structured decomposition, achieving competitive performance while maintaining cost efficiency.\n\n**Theoretical Foundation:** The core assumption that problems can be decomposed into answer-equivalent subquestions with monotonically reduced complexity naturally extends to mathematical proofs, where complex theorems can be broken down into smaller lemmas and intermediate steps that collectively establish the main result.\n\n**Mathematical Proof Construction:** While comprehensive evaluation of mathematical proof generation remains challenging due to limited standardized benchmarks and evaluation metrics in current reasoning frameworks, we conducted preliminary exploration on several mathematical proof problems. AoT's framework can decompose overall proof objectives into smaller sub-proofs, organizing the logical flow more coherently. Due to time constraints and the limited discussion of such scenarios in current reasoning literature, we can provide several illustrative cases demonstrating AoT's performance on mathematical proof tasks:\n\n**Case Study: Proving the Sum of Rational and Irrational is Irrational**\n\nThis example is adapted from ProofNet [1].\n\n**Original Problem:**\nIf $r$ is rational $(r \\neq 0)$ and $x$ is irrational, prove that $r+x$ is irrational.\n\n**Step 1: Complete Reasoning Trajectory (Standard CoT)**\nThe standard CoT approach might:\n1. Assume $r+x$ is rational\n2. Try to derive a contradiction\n3. But may have logical jumps or lack rigor in the derivation\n\n**Step 2: DAG Structure Decomposition Process**\nThe AoT framework decomposes the reasoning into a clearer DAG:\n- Node 1: Understand definitions of rational and irrational numbers\n- Node 2: Establish proof by contradiction framework\n- Node 3: Utilize closure properties of rational numbers\n- Node 4: Derive contradiction and conclude\n\nDependencies: Node 4 depends on Node 3, which depends on Nodes 1 and 2.\n\n**Step 3: Specific Execution Steps of Contraction Operations**\nThe AoT framework contracts Nodes 1 and 2 into a simpler formulation:\n\nOriginal Question: \"Prove that the sum of rational $r$ and irrational $x$ is irrational\"\n\nContracted Question: \"Assume $r+x=q$ where $q$ is rational, and use the closure property of rational numbers under subtraction to determine the nature of $x=q-r$.\"\n\nThis contraction clarifies the core insight: leveraging algebraic properties of rational numbers.\n\nRef:\n\n[1] ProofNet: Autoformalizing and Formally Proving Undergraduate-Level Mathematics. ArXiv 2024\n\n> ### Q1: Step-by-Step Example for DAG Decomposition and Contraction\n\nThank you very much for this constructive suggestion. You are absolutely right that detailed step-by-step examples are essential for understanding the DAG decomposition and contraction process. While Figure 2 demonstrates the Markov state transition process, space constraints prevent it from showing the detailed mechanisms of DAG decomposition, contraction, and evaluation steps. We will include additional examples in the appendix of our revision."}]

Author rebuttal:

Meta-review: The paper proposes a method to extract a DAG of dependencies from an overarching task by breaking it down into sub-questions that can be answered "atomically". While many concerns were raised by reviewers regarding the quality of the underlying graphs and why not to solve them directly, the authors appear to have satisfactorily answered these concerns during the rebuttal period. The only reviewer who recommends rejection VGGy has stated that they would not fight for rejection. The other reviewers also appear to be at a consensus that this work could be accepted as the claims match the empirical results and it is well executed. The approach also blends various prior approaches and bring it to the world of LLMs and as such is worth exploring further. I also lean on the side of accepting given room.
Decision: Accept (poster)