Atom of Thoughts for Markov LLM Test-Time Scaling

• URL: http://arxiv.org/abs/2502.12018v2
• Date: Sun, 23 Mar 2025 19:05:28 GMT
• Title: Atom of Thoughts for Markov LLM Test-Time Scaling
• Authors: Fengwei Teng, Zhaoyang Yu, Quan Shi, Jiayi Zhang, Chenglin Wu, Yuyu Luo,
• Abstract summary: Large Language Models (LLMs) achieve superior performance through training-time scaling.<n>As the scale of reasoning increases, existing test-time scaling methods suffer from accumulated historical information.<n>We observe that complex reasoning can be achieved by solving a series of independent and self-contained subquestions.
• Score: 18.288669306091155
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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. Experiments across six benchmarks demonstrate the effectiveness of \our both as a standalone framework and a plug-in enhancement. Notably, on HotpotQA, when applied to gpt-4o-mini, \our achieves an \textbf{80.6\%} F1 score, surpassing o3-mini by \textbf{3.4\%} and DeepSeek-R1 by \textbf{10.6\%}. The code is available at \href{https://github.com/qixucen/atom}{https://github.com/qixucen/atom}.

Related papers

• Learning to Reason Over Time: Timeline Self-Reflection for Improved Temporal Reasoning in Language Models [21.579319926212296]
  Large Language Models (LLMs) have emerged as powerful tools for generating coherent text, understanding context, and performing reasoning tasks. They struggle with temporal reasoning, which requires processing time-related information such as event sequencing, durations, and inter-temporal relationships. We introduce TISER, a novel framework that enhances the temporal reasoning abilities of LLMs through a multi-stage process that combines timeline construction with iterative self-reflection.
  arXiv  Detail & Related papers  (2025-04-07T16:51:45Z)
• Thinking Longer, Not Larger: Enhancing Software Engineering Agents via Scaling Test-Time Compute [61.00662702026523]
  We propose a unified Test-Time Compute scaling framework that leverages increased inference-time instead of larger models. Our framework incorporates two complementary strategies: internal TTC and external TTC. We demonstrate our textbf32B model achieves a 46% issue resolution rate, surpassing significantly larger models such as DeepSeek R1 671B and OpenAI o1.
  arXiv  Detail & Related papers  (2025-03-31T07:31:32Z)
• Activation-aware Probe-Query: Effective Key-Value Retrieval for Long-Context LLMs Inference [56.71209737306054]
  We propose textbfActQKV, a training-free, textbfActivation-aware approach that dynamically determines probe-textbfQuery and leverages it to retrieve the relevant textbfKV pairs for inference. Experiments on the Long-Bench and $infty$ Benchmarks demonstrate its state-of-the-art performance with competitive inference quality and resource efficiency.
  arXiv  Detail & Related papers  (2025-02-19T08:50:44Z)
• Revisiting the Test-Time Scaling of o1-like Models: Do they Truly Possess Test-Time Scaling Capabilities? [61.85289698610747]
  We study whether o1-like large language models (LLMs) truly possess test-time scaling capabilities. We find that longer CoTs of these o1-like models do not consistently enhance accuracy. We propose Shortest Majority Vote, a method that combines parallel scaling strategies with CoT length characteristics.
  arXiv  Detail & Related papers  (2025-02-17T07:21:11Z)
• Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs [76.43407125275202]
  o1-like models can emulate human-like long-time thinking during inference. This paper presents the first comprehensive study on the prevalent issue of overthinking in these models. We propose strategies to mitigate overthinking, streamlining reasoning processes without compromising accuracy.
  arXiv  Detail & Related papers  (2024-12-30T18:55:12Z)
• AtomR: Atomic Operator-Empowered Large Language Models for Heterogeneous Knowledge Reasoning [38.736190591684]
  We introduce AtomR, a framework for large language models to conduct accurate heterogeneous knowledge reasoning at the atomic level.<n>AtomR decomposes a complex question into a reasoning tree where each leaf node corresponds to an atomic knowledge operator.<n>In the reasoning execution stage, AtomR executes each atomic knowledge operator, which flexibly selects, retrieves, and operates atomic level knowledge from heterogeneous sources.
  arXiv  Detail & Related papers  (2024-11-25T15:35:51Z)
• AtomThink: A Slow Thinking Framework for Multimodal Mathematical Reasoning [70.95645743670062]
  AtomThink is a framework for constructing long chains of thought (CoT) in a step-by-step manner, guiding MLLMs to perform complex reasoning.<n>AtomMATH is a large-scale multimodal dataset of long CoTs, and an atomic capability evaluation metric for mathematical tasks.<n>AtomThink significantly improves the performance of baseline MLLMs, achieving approximately 50% relative accuracy gains on MathVista and 120% on MathVerse.
  arXiv  Detail & Related papers  (2024-11-18T11:54:58Z)
• Atomic Fact Decomposition Helps Attributed Question Answering [30.75332718824254]
  Attributed Question Answering (AQA) aims to provide both a trustworthy answer and a reliable attribution report for a question. This paper proposes an Atomic fact decomposition-based Retrieval and Editing framework. It decomposes the generated long-form answers into molecular clauses and atomic facts by the instruction-tuned LLMs.
  arXiv  Detail & Related papers  (2024-10-22T05:25:54Z)
• Path-Consistency: Prefix Enhancement for Efficient Inference in LLM [3.309813585671485]
  textitpath-consistency mitigates both the errors and redundancies from random or less useful sampling in self-consistency. textitpath-consistency achieves significant acceleration in inference latency ranging from $7.8%$ to $40.5%$.
  arXiv  Detail & Related papers  (2024-08-25T01:45:53Z)
• Integrating Large Language Models with Graph-based Reasoning for Conversational Question Answering [58.17090503446995]
  We focus on a conversational question answering task which combines the challenges of understanding questions in context and reasoning over evidence gathered from heterogeneous sources like text, knowledge graphs, tables, and infoboxes. Our method utilizes a graph structured representation to aggregate information about a question and its context.
  arXiv  Detail & Related papers  (2024-06-14T13:28:03Z)
• R-Tuning: Instructing Large Language Models to Say `I Don't Know' [66.11375475253007]
  Large language models (LLMs) have revolutionized numerous domains with their impressive performance but still face their challenges. Previous instruction tuning methods force the model to complete a sentence no matter whether the model knows the knowledge or not. We present a new approach called Refusal-Aware Instruction Tuning (R-Tuning) Experimental results demonstrate R-Tuning effectively improves a model's ability to answer known questions and refrain from answering unknown questions.
  arXiv  Detail & Related papers  (2023-11-16T08:45:44Z)
• T-SciQ: Teaching Multimodal Chain-of-Thought Reasoning via Mixed Large Language Model Signals for Science Question Answering [59.63860993280275]
  Large Language Models (LLMs) have demonstrated exceptional performance in various Natural Language Processing (NLP) tasks. We propose a novel method termed T-SciQ that aims at teaching science question answering with LLM signals. Our approach achieves a new state-of-the-art performance on the ScienceQA benchmark, with an accuracy of 96.18%.
  arXiv  Detail & Related papers  (2023-05-05T11:56:30Z)
• Time-aware Multiway Adaptive Fusion Network for Temporal Knowledge Graph Question Answering [10.170042914522778]
  We propose a novel textbfTime-aware textbfMultiway textbfAdaptive (textbfTMA) fusion network. For each given question, TMA first extracts the relevant concepts from the KG, and then feeds them into a multiway adaptive module. This representation can be incorporated with the pre-trained KG embedding to generate the final prediction.
  arXiv  Detail & Related papers  (2023-02-24T09:29:40Z)
• Augmenting Pre-trained Language Models with QA-Memory for Open-Domain Question Answering [38.071375112873675]
  We propose a question-answer augmented encoder-decoder model and accompanying pretraining strategy. This yields an end-to-end system that outperforms prior QA retrieval methods on single-hop QA tasks.
  arXiv  Detail & Related papers  (2022-04-10T02:33:00Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  We study a new subclass of POMDPs, whose latent states can be decoded by the most recent history of a short length $m$. In particular, in the rich-observation setting, we develop new algorithms using a novel "moment matching" approach with a sample complexity that scales exponentially. Our results show that a short-term memory suffices for reinforcement learning in these environments.
  arXiv  Detail & Related papers  (2022-02-08T16:39:57Z)
• Intervention Efficient Algorithm for Two-Stage Causal MDPs [15.838256272508357]
  We study Markov Decision Processes (MDP) wherein states correspond to causal graphs that generate rewards. In this setup, the learner's goal is to identify atomic interventions that lead to high rewards by intervening on variables at each state. Generalizing the recent causal-bandit framework, the current work develops (simple) regret minimization guarantees for two-stage causal MDPs.
  arXiv  Detail & Related papers  (2021-11-01T12:22:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.