Research map / Large language models / Reasoning and chain of thought
Atom of Thoughts for Markov LLM Test-Time Scaling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Atom of Thoughts (AoT), a Markovian reasoning process that decomposes each question into a DAG and contracts it into a simpler answer-equivalent question, which integrates with tree search and reflection and yields emergent atomic reasoning units.
Problem
Test-time scaling methods such as CoT, ToT and GoT accumulate historical reasoning context, which wastes compute and interferes with reasoning as reasoning scale grows.
Approach
Replace accumulated reasoning history with a Markov chain of self-contained, answer-equivalent subquestions: each transition decomposes the current question into a temporary DAG of dependencies, discards independent nodes, and contracts the dependent part into a simpler next question, with an LLM judge selecting the best answer across states to terminate safely.
Key results
- With GPT-4o-mini, AoT scores 83.6 on MATH, 95.0 on GSM8K, 75.2 on MBPP and 68.5 on LongBench, the top result in the table versus 78.3 for CoT on MATH.
- With O3-mini, AoT reaches 83.0 on AIME and 32.2 on LiveCodeBench, the highest among compared methods.
- Integrating ToT with Markov chain and reflective refinement gives 84.9% on MATH (vs ToT 82.0%) and 81.2% on AIME (vs ToT 78.0%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AoT instead of FoT | GPT-4o-mini · GSM8K | score: 94.2 -> 95.0 | Helped |
| Use AoT instead of FoT | GPT-4o-mini · MBPP | score: 74.8 -> 75.2 | Helped |
| Use AoT instead of AFlow | GPT-4o-mini · LongBench | score: 61.0 -> 68.5 | Helped |
| Use AoT instead of AFlow | DeepSeek-V3 · MATH | score: 96.1 -> 96.5 | Helped |
| Use AoT instead of AFlow | DeepSeek-V3 · GSM8K | score: 97.8 -> 98.2 | Helped |
| Use AoT instead of FoT | DeepSeek-V3 · MBPP | score: 78.2 -> 79.6 | Helped |
| Use AoT instead of AFlow | DeepSeek-V3 · LongBench | score: 63.5 -> 71.0 | Helped |
| Use AoT instead of AFlow | O3-mini · AIME | score: 82.5 -> 83.0 | Helped |
| Use AoT instead of FoT | O3-mini · LiveCodeBench | score: 27.8 -> 32.2 | Helped |
| Use AoT instead of FoT | O3-mini · LongBench | score: 57.9 -> 65.3 | Helped |
| Use AoT instead of AFlow | DeepSeek-R1 · AIME | score: 81.2 -> 81.7 | Helped |
| Use AoT instead of FoT | DeepSeek-R1 · LiveCodeBench | score: 28.1 -> 30.9 | Helped |
Surprising findings
- Partial structural cues (ablation without DAG-guided contraction) hurt performance more than providing no structure at all, according to the authors.
Limitations
- Relies on LLM judge selection and LLM-based decomposition, so quality depends on the backbone's ability.
- Deeper chains and atomic re-execution incur significantly higher computational cost.
Experimental setup
Datasets: MATH GSM8K MBPP LiveCodeBench AIME HotpotQA MuSiQue 2WikiMultiHopQA LongBench
Benchmarks: MATH GSM8K AIME MBPP LiveCodeBench LongBench
Metrics: pass rate F1
Baselines: CoT CoT-SC Self-Refine Analogical Prompting AFlow ToT GoT FoT
Builds on: Chain-of-Thought Tree of Thoughts Least-to-Most prompting Forest of Thoughts AFlow
Closest papers by meaning
- Let Me Think! A Long Chain of Thought Can Be Worth Exponentially Many Short Ones (NeurIPS 2025 · similarity 0.90)
- Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for LLM Problem-Solving (ICLR 2025 · similarity 0.89)
- Plan and Budget: Effective and Efficient Test-Time Scaling on Reasoning Large Language Models (ICLR 2026 · similarity 0.89)
- Markovian Transformers for Informative Language Modeling (ICLR 2026 · similarity 0.89)
- A Theoretical Study on Bridging Internal Probability and Self-Consistency for LLM Reasoning (NeurIPS 2025 · similarity 0.89)
- Towards Thinking-Optimal Scaling of Test-Time Compute for LLM Reasoning (NeurIPS 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.