Authors: Xiaofan Zhou, Huy Nguyen, Bo Yu, Chenxi Liu, Lu Cheng
Organizations: Department of Computer Science, University of Illinois Chicago, Chicago, IL 60607, USA · Data science, Augustana College, Rock Island, IL 61201, USA · Department of Civil and Environmental Engineering, University of Utah, Salt Lake City, UT 84112, USA
Large Language Models (LLMs) increasingly rely on multi-turn reasoning and interaction, such as adaptive retrieval-augmented generation (RAG) and ReAct-style agents, to answer difficult questions. These methods improve accuracy by iteratively retrieving information, reasoning, or acting, but introduce a key challenge: When should the model stop? Existing approaches rely on heuristic stopping rules or fixed turn budgets and provide no formal guarantees that the final prediction still contains the correct answer. This limitation is particularly problematic in high-stakes domains such as finance and healthcare, where unnecessary turns increase cost and latency, while stopping too early risks incorrect decisions. Conformal prediction (CP) provides formal coverage guarantees, but existing LLM-CP methods only apply to a single model output and cannot handle multi-turn pipelines with adaptive stopping. To address this gap, we propose Multi-Turn Language Models with Conformal Prediction (MiCP), the first CP framework for multi-turn reasoning. MiCP allocates different error budgets across turns, enabling the model to stop early while maintaining an overall coverage guarantee. We demonstrate MiCP on adaptive RAG and ReAct, where it achieves the target coverage on both single-hop and multi-hop question answering benchmarks while reducing the number of turns, inference cost, and prediction set size. We further introduce a new metric that jointly evaluates coverage validity and answering efficiency.
Figures & tables
Figure 1: MiCP pipeline.
Figure 2: Empirical gold retention rate vs. the target 1−α across five datasets on adaptive RAG and ReAct for retrieval calibration. All models maintain coverage at or above the 1−α guarantee for all tested error rates.
Figure 3: Empirical coverage rate vs. the target 1−α across five datasets on adaptive RAG and ReAct for the final prediction set. All models maintain coverage at or above the 1−α guarantee for all tested error rates.
Qwen3.5-9B
Gemma-2-9B-IT
GPT-4o-mini
Dataset
Ours
w/o ES
Avg Iter
Answer Rate
Ours
w/o ES
Avg Iter
Answer Rate
Ours
w/o ES
Avg Iter
Answer Rate
Avg #Turns
HotpotQA
2.562
3.000
2.331
2.433
2.782
3.000
2.481
2.854
2.497
3.000
2.173
2.607
HotpotQA (React)
2.522
3.000
2.313
2.557
2.752
3.000
2.472
2.757
2.587
3.000
2.167
2.877
NQ
2.621
3.000
2.459
2.770
2.840
3.000
2.597
2.856
3.000
3.000
2.849
2.924
TriviaQA
2.528
3.000
2.356
2.587
2.898
3.000
2.687
2.806
2.494
3.000
2.494
2.641
MuSiQue
2.705
3.000
2.519
2.861
2.795
3.000
2.488
2.681
2.870
3.000
2.278
2.936
Table 1: Average number of retrieval turns (Avg #Turns), prediction set size, and composite objective across five datasets, averaged over all α values. Bold indicates the best result per row. Lower is better for all metrics. w/o ES means no early stop.
As LLM reasoning performance plateaus, 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 diverse agentic benchmarks demonstrate that TAB achieves a superior accuracy-cost tradeoff saving up to 35% tokens and reducing latency up to 30% while maintaining accuracy over static and off-the-shelf LLM budget baselines. Further, for systems where a plan of all turns is available apriori, we propose TAB All-SubQ, a budget allocation policy that budgets tokens based on the conversation history and entire plan saving up to 40% tokens over baselines.
While LLMs demonstrate strong reasoning capabilities when provided with full information in a single turn, they exhibit substantial vulnerability in multi-turn interactions. Specifically, when information is revealed incrementally or requires updates, models frequently fail to integrate new constraints, leading to a collapse in performance compared to their single-turn baselines. We term the root cause as Contextual Inertia: a phenomenon where models rigidly adhere to previous reasoning traces. Even when users explicitly provide corrections or new data in later turns, the model ignores them, preferring to maintain consistency with its previous (incorrect) reasoning path. To address this, we introduce Reinforcement Learning with Single-Turn Anchors (RLSTA), a generalizable training approach designed to stabilize multi-turn interaction across diverse scenarios and domains. RLSTA leverages the model's superior single-turn capabilities as stable internal anchors to provide reward signals. By aligning multi-turn responses with these anchors, RLSTA empowers models to break contextual inertia and self-calibrate their reasoning based on the latest information. Experiments show that RLSTA significantly outperforms standard fine-tuning and abstention-based methods. Notably, our method exhibits strong cross-domain generalization (e.g., math to code) and proves effective even without external verifiers, highlighting its potential for general-domain applications. Code is available at https://github.com/Tencent/RLSTA.
Xingwu Chen, Zhanqiu Zhang, Yiwen Guo +1
School of Computing and Data Science, The University of Hong Kong · LIGHTSPEED · Independent Researcher
By incorporating test-time compute scaling, large reasoning models (LRMs) can solve complex problems through explicit chain-of-thought (CoT) reasoning processes. However, they often suffer from overthinking, resulting in redundant token outputs and degraded accuracy. Current methods to mitigate this issue remain limited: training-based approaches require substantial computational resources, while training-free methods rely on well-crafted prompts or unreliable confidence signals. In this work, we investigate early stopping from the perspective of attention distributions and propose a simple method, ASAG, which infers the model's reasoning state and adaptively adjusts the generation strategy. The proposed framework is training-free and plug-and-play, enabling seamless integration into existing LRMs. Extensive experiments on nine benchmarks demonstrate consistent improvements across mainstream LRMs with varying parameter scales, including the DeepSeek-R1-Distill and Qwen3 series. Specifically, ASAG improves average accuracy by 3.2% while reducing the number of generated tokens by nearly 40% across all reasoning tasks on Qwen3-8B.
Jiakai Li, Ke Qin, Rongzheng Wang +4
University of Electronic Science and Technology of China, Chengdu, China · Ubiquitous Intelligence and Trusted Services Key Laboratory of Sichuan Province, Chengdu, China