--- title: "Not All Turns Are Equally Hard: Adaptive Thinking Budgets For Efficient Multi-Turn Reasoning" authors: ["Neharika Jali, Anupam Nayak & Gauri Joshi", "Carnegie Mellon University"] url: "https://arxiv.org/abs/2604.05164" sections: 33 estimated_tokens: "16.1k" --- ## Contents - 1 Introduction - Main Contributions. - 2 Related Works - 3 TAB: Turn-Adaptive Budgets - 3.1 Problem Setting - Notation. - Need for Sequential Decision Making in Multi-Turn Systems. - 3.2 Multi-Turn Reasoning as a Markov Decision Process - 3.3 Training Turn-Adaptive Budget Allocation Policy via GRPO - Reward Function. - Advantage Estimation and Policy Optimization. - 3.4 Inference in Multi-Turn Reasoning System with TAB - 4 Experiments - 4.1 Setup - Multi-Turn Reasoning and Models. - Datasets and Baselines. - Budget Allocation Policy Training. - 4.2 Results - Accuracy-tokens tradeoff. - Budget Allocation Policy Characteristics. - TAB All-SubQ: Planning and Value of Future Context. - Out of Distribution Problems. - Budget Model Scaling. - 5 Conclusion - Acknowledgments - References - Appendix - LLM Usage - Appendix A Experiment Results - Appendix B Multi-Turn Reasoning Trajectory Examples - B.1 Token Savings via Adaptive Allocation - B.2 Effect of Early-Stage Budgets on Later Quality - Appendix C Prompts ## Abstract 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 % 40\% tokens over baselines. ## 1 Introduction Figure: Figure 1: On the left is a multi-turn reasoning trajectory with a sub-question of varying difficulty presented at every turn. Adaptive difficulty level based per-turn token budget allocations result in improved utilization of compute. On the right is a multi-turn system where at every turn $t$ at inference (colored blocks), the user presents a sub-question $q_{t}$, the budget allocation policy allots a token budget $b_{t}$ based on the conversation history $x_{1:t-1}$ and $q_{t}$ to the solver which then generates a response $y_{t}$. The Budgeter is trained via GRPO with a reward function that is a combination of accuracy and number of tokens used. Refer to caption: 2604.05164v2/x1.png As recent gains in LLM reasoning increasingly come from test-time computation (Wu et al., 2025; Muennighoff et al., 2025; Snell et al., 2024), a central deployment question is no longer only how to scale inference, but how to spend that inference budget well. Efficient reasoning matters not only because it reduces cost, but also because it enables more effective test-time scaling under fixed resources. The same compute budget can be used more productively by reserving deeper reasoning for the steps that matter most, or by supporting more candidate solutions and more requests overall. This also matters at the systems level. Under real-world multi-user serving workloads, unnecessary reasoning increases latency, memory use, and long-context processing costs, which reduces throughput (Agrawal et al., 2024; Sun et al., 2024). Prior systems work further shows that these serving bottlenecks become more pronounced for longer sequences and long-context inference (Kwon et al., 2023; Hooper et al., 2025). Current approaches to efficient test-time reasoning largely follow a common philosophy. They first estimate the difficulty of a problem, then allocate an appropriate amount of compute, and finally solve the problem under that budget (Wang et al., 2025b; Shen et al., 2025; Zhang et al., 2025b). In this sense, most existing methods treat efficient reasoning as a one-shot allocation problem at the level of an entire instance. Multi-turn reasoning, often introduced via task or sub-question decomposition to improve performance, makes efficient compute allocation even more important. In single-turn settings, wasted compute is local and an unnecessarily long trace only slows and increases the cost of one response. In multi-turn settings, however, inefficiency compounds over time (Jeong and Ahn, 2025; Gao et al., 2024). Tokens generated early become part of later context, increasing memory, bandwidth, and long-context serving costs as the interaction proceeds (Agrawal et al., 2024; Qin et al., 2025). This is especially problematic in decomposed pipelines, where some sub-questions are routine while others are decisive (Zeng et al., 2025); uniform or myopic per-turn budgets can therefore waste compute on bookkeeping steps and under-invest in the turns that matter most. Yet, compared with single-turn efficient reasoning, multi-turn budget allocation remains relatively underexplored. In this work, we cast multi-turn reasoning as a distinct sequential compute allocation problem. This setting is challenging for several reasons. First, it is characterized by strong *temporal dependency* across turns. A budget decision at the current turn affects not only the immediate response quality, but also the remaining compute, the downstream reasoning trajectory, and the final task outcome, all without visibility into future sub-questions. Second, feedback is delayed. Since rewards are observed, or correctness is verified, only at the end of the trajectory, the problem involves difficult *credit assignment* across turn-level decisions. Finally, the objective is inherently *multi-objective*. A successful approach must jointly optimize task accuracy and token efficiency over entire reasoning trajectories. Together, these properties make multi-turn budget allocation fundamentally different from single-turn budget selection and render existing single-turn efficiency methods non-trivial to extend to this setting. #### Main Contributions. We address the problem of compute efficiency in multi-turn reasoning in the following manner. - 1. We formulate multi-turn reasoning as a sequential compute allocation problem, formalized as a multi-objective Markov Decision Process (MDP). 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. - 2. We demonstrate that TAB achieves a superior accuracy-tokens tradeoff compared to static and off-the-shelf LLM-Judge baselines saving up to $35\%$ tokens while improving or maintaining accuracy on math reasoning benchmarks. - 3. For systems where a plan of all sub-questions is available apriori, we propose a variant TAB All-SubQ, a budget allocation policy that allots tokens as a function of the conversation trajectory thus-far and all sub-questions. It saves up to $40\%$ tokens over baselines strengthening our claim of multi-turn reasoning efficiency being a planning problem rather than an individual difficulty-estimation problem. ## 2 Related Works Inference Time Budget Adaptation Methods. Inference-time interventions are increasingly used to improve reasoning efficiency by allocating computation more selectively. One common strategy is model routing, which directs easier queries to smaller or specialized LLMs while reserving larger models for more difficult instances (Ding et al., 2024; Zhang et al., 2025a; Shao et al., 2024; Ong et al., 2025; Patel et al., 2025). Related work has also explored token-level routing, which enables finer-grained compute allocation within a single generation rather than only at the query level (Kapoor et al., 2026). These ideas have further been extended to agentic settings, where routing decisions must additionally account for downstream execution costs (Zhang et al., 2026; Qian et al., 2025). Another line of work focuses on estimating question difficulty before assigning a reasoning budget (Wang et al., 2025b; Shen et al., 2025; Huang et al., 2025), while other approaches dynamically switch between thinking and non-thinking modes based on estimated difficulty (Zhang et al., 2025b). More recently, adaptive budget forcing methods have been proposed, using signals such as confidence or token entropy to decide whether additional reasoning is needed (Yuan et al., 2025; Li et al., 2026). However, most of these methods are designed for single-turn interactions and do not naturally support planning or budget allocation across multi-turn settings, where reasoning costs must be managed adaptively over the course of an interaction. Further, methods for model routing in multi-turn conversations often incur significant infrastructure overheads of hosting multiple model variants, the prefill and/or decode latency associated with cross-model transitions and cost of extra model invocations. Inference Time Planning. Complementary to the budget adaptation methods are task Task decomposition (TD) methods that aim to improve performance by decomposing difficult problems into simpler subproblems that can be solved sequentially. Well before GRPO-style post-training became prevalent, prompting-based TD methods had already shown substantial benefits from explicitly structuring intermediate reasoning (Wei et al., 2022; Radhakrishnan et al., 2023; Wang et al., 2023; Khot et al., 2023). More recent reasoning-oriented work has revisited this paradigm by using a stronger model to generate a decomposition or plan and a smaller model to execute the corresponding subtasks (Lin et al., 2026; Xin et al., 2025). This strategy has also been widely adopted in agent-based frameworks (Qian et al., 2025; Erdogan et al., 2025). More recently, hierarchical RL approaches have sought to endow models with subgoal decomposition capabilities through training (Wang et al., 2025a; Ge et al., 2025; Ren et al., 2025). Nevertheless, the primary focus of most of these methods has been on improving task performance, rather than on enabling more efficient reasoning. Training Efficient Reasoners. Following the observation that GRPO-based post-training tends to increase the average length of model responses as training progresses, a growing body of work has sought to mitigate overthinking in LLMs and improve token-efficient reasoning, especially on easier problems. One prominent line of research modifies the training objective by incorporating length penalties or related mechanisms to encourage shorter reasoning traces (Arora and Zanette, 2025; Aggarwal and Welleck, 2025; Ayoub et al., 2026; Liu et al., 2026; Qi et al., 2025). Other approaches rely on oversampling and training on shorter responses (Shrivastava et al., 2025), adopt two-stage training procedures (Song and Zheng, 2025; Fatemi et al., 2025). More recently, several works have also explored training efficient reasoners through self-distillation (Zhao et al., 2026; Sang et al., 2026). The central challenge is to reduce unnecessary verbosity without making the model overly conservative, which can hinder exploration at test time. These works can be seen as developing efficient low-level solvers that may be leveraged as a part of a bigger system at inference time. ## 3 TAB: Turn-Adaptive Budgets In this section, we formulate the efficient multi-turn reasoning problem as a sequential compute allocation problem instead of a single-response length-control problem. We model this as a multi-objective Markov decision process and propose TAB: Turn-Adaptive Budgets, a budget allocation policy learned via the GRPO algorithm with a reward function that is a convex combination of the accuracy and adherence to global token budget. ### 3.1 Problem Setting #### Notation. In this work, we study multi-turn reasoning under a global per-problem token budget. Consider a large language model $f_{\theta}(\cdot)$ with a set of token budgets ${\mathcal{B}}$ that generates response $y$ to query $q$ by respecting the allotted token budget $b\in{\mathcal{B}}$ as $y\sim f_{\theta}(q;b)$ (Aggarwal and Welleck, 2025). A multi-turn problem instance $x$ consists of a sequence of turns, $t\in[T]$, with sub-questions $q_{t}$ presented to the language model and its responses $y_{t}$ as $x=(q_{1},y_{1},q_{2},y_{2},\dots,q_{T},y_{T})$ where $T$ is the total number of turns in the conversation episode. Denote the conversation up to turn $t$ by $x_{1:t}=(q_{1},y_{1},\dots,q_{t},y_{t})$. If at each turn $t$, a budget allocation policy $\pi_{\phi}$, parameterized by $\phi$, selects how much reasoning compute $b_{t}\in{\mathcal{B}}$ to allocate to the solver LLM, the response generated can be represented as $y_{t}\sim f_{\theta}(x_{1:t-1},q_{t};b_{t}).$ #### Need for Sequential Decision Making in Multi-Turn Systems. Current reasoning models are prone to overthinking and spending far too many tokens on easy turns of a multi-turn conversation leaving little budget for later harder turns. Unlike for single-turn tasks, as demonstrated in [Figure 2](#S4.F2), static and context-unaware individual sub-question difficulty based token budget policies are ineffective in the multi-turn setting which present the following set of challenges. First is the *temporal dependency* and its inherently sequential nature where compute allocation decisions at the current turn made without seeing the future sub-questions determine the future resources remaining, downstream reasoning trajectory and eventual problem accuracy in addition to the quality of the immediate response. Second is the challenge of delayed feedback where rewards presented or accuracy verifiable only at the end of the trajectory resulting in the *credit-assignment* problem making it difficult to discern which specific turn-level budget decisions contributed to the final outcome. Finally, the problem requires a *multi-objective optimization* algorithm that can optimize over sequential trajectories to effectively learn the accuracy-tokens tradeoff. ### 3.2 Multi-Turn Reasoning as a Markov Decision Process We frame the sequential allocation of token budgets as a scalarized multi-objective MDP as follows (Roijers et al., 2013; Van Moffaert and Nowé, 2014). Consider a Markov decision process ${\mathcal{M}}$. The state at turn $t$ represents the problem trajectory so far including all the previous sub-questions and responses and the current sub-question $s_{t}=[x_{1:t-1},q_{t}]$. The action represents the token budget chosen $b_{t}\sim\pi_{\phi}(\cdot|x_{1:t-1,q_{t}})$. The transition to the next state consists of concatenating the response generated by the solver LLM $y_{t}$ to the problem trajectory as $x_{1:t}=(q_{1},y_{1},\dots,q_{t},y_{t})$. Consider reasoning tasks with verifiable rewards and represent accuracy of the generated solution as $\text{acc}(x)=\mathbb{1}_{y_{T}=y^{\star}_{T}}$ where $y_{T}^{\star}$ represents the ground truth label. The objective of the MDP, thus, is to find an optimal budget allocation policy $\pi^{\star}_{\phi}$ that maximizes the expected accuracy of the reasoning task subject to a global token budget $B$ modelled as a soft penalty as $$ $\pi^{\star}_{\phi}=\operatorname*{arg\,max}_{\pi}\mathbb{E}_{x,\pi}\left[\text{acc}(x)-\lambda\max\left(0,\sum_{t=1}^{T}b_{t}-B\right)\right],$ (1) $$ where the budget violation penalty weight $\lambda$ characterizes the trade-off between accuracy and token efficiency. Alternative reward scalarizations can also be designed to promote concise reasoning, including exact-target, maximum-length, and smoother sigmoid-based penalties (Aggarwal and Welleck, 2025; Arora and Zanette, 2025; Ayoub et al., 2026). We use a hinge penalty because our goal is not to match a target length, but to discourage violating a global per-problem budget. This formulation aligns closely with the deployment objective and is less susceptible than naive additive penalties to pathological under-allocation. ### 3.3 Training Turn-Adaptive Budget Allocation Policy via GRPO #### Reward Function. We learn the optimal budget allocation policy $\pi^{\star}_{\phi}(b_{t}|x_{1:t-1},q_{t})$ where $b_{t}\in{\mathcal{B}}$ using the Group Relative Policy Optimization (GRPO) algorithm (Shao et al., 2024) as follows. Note that we adopt GRPO over Proximal Policy Optimization (PPO) (Schulman et al., 2017) as it eliminates the need for a learned value function, which is notoriously difficult to estimate accurately in long-horizon, sparse-reward settings such as multi-turn reasoning. Now, for each training problem $i$, we sample a group of $G$ multi-turn trajectories $\{x^{(i,g)}\}_{g=1}^{G}$. Recall that for every turn $t$ of a trajectory, the budget allocator observes the current conversation state, $[x_{1:t-1}^{(i,g)},q_{t}^{(i,g)}]$, chooses the budget tokens by sampling $b_{t}^{(i,g)}\sim\pi_{\phi}(\cdot|x_{1:t-1}^{(i,g)},q_{t}^{(i,g)})$ and supplies it to the LLM, which generates the response $y_{t}^{(i,g)}\sim f_{\theta}(x_{1:t-1}^{(i,g)},q_{t}^{(i,g)};b_{t}^{(i,g)})$. After the final synthesis step, each trajectory receives a single terminal reward $r^{(i,g)}$ that scalarizes correctness and token efficiency. We design the reward function(^1^11Note that while training, we use the number of tokens actually used by the solver LLM at every turn instead of the number of tokens allotted by the budget policy.) to learn the optimal policy ([1](#S3.E1)) as $$ $r^{(i,g)}\left(x^{(i,g)}\right)=\text{acc}\left(x^{(i,g)}\right)-\lambda\max\left(0,\sum_{t=1}^{T}b_{t}^{(i,g)}-B\right)$ (2) $$ where $\text{acc}(x)\in\{0,1\}$ denotes the correctness of the generated solution, $B$ is the target global token budget and $\lambda$ is a penalty weight. #### Advantage Estimation and Policy Optimization. Following GRPO, rewards are normalized within each group $G$ and advantages estimated as $$ $\hat{A}^{(i,g)}=\frac{r^{(i,g)}-\mu^{(i)}}{\sigma^{(i)}}\quad\quad\text{where}\quad\quad\mu^{(i)}=\mathrm{mean}\!\left(\{r^{(i,g)}\}_{g=1}^{G}\right),\sigma^{(i)}=\mathrm{std}\!\left(\{r^{(i,g)}\}_{g=1}^{G}\right).$ $$ Note that since the reward is terminal and obtained at the end of the trajectory, the same trajectory-level advantage $\hat{A}^{(i,g)}$ is assigned to all turns $t$ in $x^{(i,g)}$. We then maximize a clipped policy objective over all turn-level actions, without a value network as $$ $\displaystyle{\mathcal{J}}_{GRPO}(\phi)=\mathbb{E}_{x^{(i,g)}}\left[\frac{1}{|b_{t}^{(i,g)}|}\sum_{k=1}^{|b_{t}^{(i,g)}|}\min\left(\rho^{(i,g)}_{t,