Not All Turns Are Equally Hard: Adaptive Thinking Budgets For Efficient Multi-Turn Reasoning

• URL: http://arxiv.org/abs/2604.05164v2
• Date: Tue, 14 Apr 2026 01:25:23 GMT
• Title: Not All Turns Are Equally Hard: Adaptive Thinking Budgets For Efficient Multi-Turn Reasoning
• Abstract summary: We formulate multi-turn reasoning as a sequential compute allocation problem and model it as a multi-objective Markov Decision Process.<n>We propose TAB: Turn-Adaptive Budgets, a budget allocation policy that learns to maximize task accuracy while respecting global per-problem token constraints.<n>For systems where a plan of all sub-questions is available apriori, we propose TAB All-SubQ, a budget allocation policy that budgets tokens based on the conversation history and all past and future sub-questions saving up to 40% tokens over baselines.
• Score: 14.194667934432443
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: As LLM reasoning performance plateau, improving inference-time compute efficiency is crucial to mitigate overthinking and long thinking traces even for simple queries. Prior approaches including length regularization, adaptive routing, and difficulty-based budget allocation primarily focus on single-turn settings and fail to address the sequential dependencies inherent in multi-turn reasoning. In this work, we formulate multi-turn reasoning as a sequential compute allocation problem and model it as a multi-objective Markov Decision Process. We propose TAB: Turn-Adaptive Budgets, a budget allocation policy trained via Group Relative Policy Optimization (GRPO) that learns to maximize task accuracy while respecting global per-problem token constraints. Consequently, TAB takes as input the conversation history and learns to adaptively allocate smaller budgets to easier turns and save appropriate number of tokens for the crucial harder reasoning steps. Our experiments on mathematical reasoning benchmarks demonstrate that TAB achieves a superior accuracy-tokens tradeoff saving up to 35% tokens while maintaining accuracy over static and off-the-shelf LLM budget baselines. Further, for systems where a plan of all sub-questions is available apriori, we propose TAB All-SubQ, a budget allocation policy that budgets tokens based on the conversation history and all past and future sub-questions saving up to 40% tokens over baselines.

Related papers

• Thinking Economically: A Hierarchical Framework for Adaptive-Complexity Reasoning in LLMs [36.73612668202756]
  HAB learns step-specific token budgeting signals from PPL-derived step comparisons.<n>Experiments on GSM8K and MATH500 show that HAB not only surpasses standard CoT in accuracy but also reduces token usage.
  arXiv  Detail & Related papers  (2026-05-31T11:20:00Z)
• AdaptR1: Reinforcement Learning Based Adaptive Interleaved Thinking in Multi-hop Question Answering [76.52199013231484]
  We introduce AdaptR1, a Reinforcement Learning (RL) based framework for adaptive interleaved thinking in multi-hop Question Answering (QA)<n>Under the Graph-R1 setting, AdaptR1 reduces average think tokens by 69.71%, with a 90.35% reduction on HotpotQA.<n>Our analysis reveals that overthinking in multi-hop reasoning is not uniformly distributed but occurs predominantly during the initial planning stages.
  arXiv  Detail & Related papers  (2026-05-29T09:34:45Z)
• Avoiding Overthinking and Underthinking: Curriculum-Aware Budget Scheduling for LLMs [1.7499351967216341]
  Budget-Adaptive Curriculum Reasoning (BCAE) is a unified framework that jointly optimize reasoning quality and token efficiency.<n>BCAE includes a emphbudget-conditioned unified policy, a emphcurriculum-aware budget scheduler, and a emphtruncation-aware dense reward mechanism.
  arXiv  Detail & Related papers  (2026-03-29T18:31:09Z)
• Conformal Thinking: Risk Control for Reasoning on a Compute Budget [60.65072883773352]
  Reasoning Large Language Models (LLMs) enable test-time scaling, with dataset-level accuracy improving as the token budget increases.<n>We re-frame the budget setting problem as risk control, limiting the error rate while minimizing compute.<n>Our framework introduces an upper threshold that stops reasoning when the model is confident and a novel lower threshold that preemptively stops unsolvable instances.
  arXiv  Detail & Related papers  (2026-02-03T18:17:22Z)
• Predictive Scheduling for Efficient Inference-Time Reasoning in Large Language Models [6.002670452103349]
  Large language models (LLMs) achieve state-of-the-art accuracy on complex reasoning tasks.<n>But using a fixed token budget per query leads to over-computation on easy inputs and under-computation on hard ones.<n>We introduce Predictive Scheduling, a plug-and-play framework that pre-runs lightweight predictors to estimate each query's optimal reasoning length or difficulty before any full generation.
  arXiv  Detail & Related papers  (2026-02-01T13:58:23Z)
• Optimal Budgeted Adaptation of Large Language Models [8.207283283207138]
  Trade-off between labeled data availability and downstream accuracy remains a central challenge in large language models.<n>We propose a principled framework for emphbudget-aware supervised fine-tuning by casting LLM adaptation as a contextual Stackelberg game.
  arXiv  Detail & Related papers  (2026-02-01T01:08:15Z)
• Budget-Aware Anytime Reasoning with LLM-Synthesized Preference Data [57.996437077411315]
  We study the reasoning behavior of large language models (LLMs) under limited computation budgets.<n>We introduce an anytime reasoning framework and the Anytime Index, a metric that quantifies how effectively solution quality improves as reasoning tokens increase.<n> Experiments on NaturalPlan (Trip), AIME, and GPQA datasets show consistent gains across Grok-3, GPT-oss, GPT-4.1/4o, and LLaMA models.
  arXiv  Detail & Related papers  (2026-01-16T07:09:30Z)
• ROI-Reasoning: Rational Optimization for Inference via Pre-Computation Meta-Cognition [11.094392304740134]
  We study budgeted inference-time reasoning for multiple tasks under a strict global token constraint.<n>This perspective highlights a meta-cognitive requirement -- anticipating task difficulty, estimating return over investment.<n>We propose ROI-Reasoning, a two-stage framework that endows LLMs with intrinsic, budget-aware rationality.
  arXiv  Detail & Related papers  (2026-01-07T11:30:55Z)
• e1: Learning Adaptive Control of Reasoning Effort [88.51897900019485]
  Increasing the thinking budget of AI models can significantly improve accuracy, but not all questions warrant the same amount of reasoning.<n>Users may prefer to allocate different amounts of reasoning effort depending on how they value output quality versus latency and cost.<n>We propose Adaptive Effort Control, a self-adaptive reinforcement learning method that trains models to use a user-specified fraction of tokens.
  arXiv  Detail & Related papers  (2025-10-30T23:12:21Z)
• HiPO: Hybrid Policy Optimization for Dynamic Reasoning in LLMs [54.16300997612526]
  Large Language Models (LLMs) increasingly rely on Chain-of-Thought (CoT) reasoning to improve accuracy on complex tasks.<n>This paper introduces the Hybrid Policy Optimization (i.e., HiPO), a framework for adaptive reasoning control.<n> Experiments across mathematics and coding benchmarks demonstrate that HiPO can substantially reduce token length while maintaining or improving accuracy.
  arXiv  Detail & Related papers  (2025-09-28T16:46:12Z)
• Hierarchical Budget Policy Optimization for Adaptive Reasoning [49.621779447691665]
  We present Hierarchical Budget Policy Optimization (HBPO), a reinforcement learning framework that enables models to learn problem-specific reasoning depths without sacrificing capability.<n>HBPO partitions the exploration space into budget-constrained hierarchies (512-2560 tokens), each with differentiated reward structures that preserve both efficiency incentives and reasoning capabilities.<n>Extensive experiments demonstrate that HBPO reduces average token usage by up to 60.6% while improving accuracy by 3.14% across four reasoning benchmarks.
  arXiv  Detail & Related papers  (2025-07-21T17:52:34Z)
• Steering LLM Thinking with Budget Guidance [48.65894557568655]
  Budget guidance is a method for steering the reasoning process of LLMs toward a target budget without requiring any fine-tuning.<n>Our approach introduces a lightweight predictor that models a Gamma distribution over the remaining thinking length.<n>This signal is then used to guide generation in a soft, token-level manner, ensuring that the overall reasoning trace adheres to the specified thinking budget.
  arXiv  Detail & Related papers  (2025-06-16T17:57:05Z)

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.