Adaptive Stopping for Multi-Turn LLM Reasoning

1. Problem Statement

Large Language Models (LLMs) increasingly rely on multi-turn reasoning (e.g., Adaptive Retrieval-Augmented Generation (RAG) and ReAct-style agents) to solve complex problems. These systems iteratively retrieve information, reason, or act until a final answer is reached. However, a critical challenge remains: deciding when to stop.

• Current Limitations: Existing methods use heuristic stopping rules (e.g., confidence thresholds, fixed turn budgets). These lack formal guarantees that the final prediction contains the correct answer.
• Risks: Stopping too early leads to incorrect answers; continuing too long increases latency, cost, and the risk of accumulating errors (noise).
• Gap in Conformal Prediction (CP): While CP provides finite-sample coverage guarantees (ensuring the correct answer is in the prediction set with probability $1-\alpha$), existing CP methods for LLMs are designed for single-shot outputs. They cannot handle the sequential, adaptive nature of multi-turn pipelines where the number of turns varies per question. Naively applying CP at each turn fails to guarantee overall coverage and incurs combinatorial sampling costs.

2. Methodology: MiCP (Multi-Turn Language Models with Conformal Prediction)

The authors propose MiCP, the first CP framework specifically designed for multi-turn LLM reasoning. It integrates three core components:

A. Problem Formulation

MiCP treats the multi-turn process as a sequence of states $r_i = (r_i^0, \dots, r_i^{T-1})$. The goal is to determine a stopping time $t^*$ and construct a prediction set $C(x)$ that satisfies:
$$P(y \in C(x)) \geq 1 - \alpha$$
where $y$ is the ground truth. The set $C(x)$ must either contain the correct answer or include a "Can't Answer" label if confidence is insufficient.

B. Stage 1: Retrieval Filtering (Calibration)

To prevent irrelevant retrieved documents from polluting the context:

• Optimistic Relevance: For each gold passage, the system calculates the maximum relevance score across all turns it appears in.
• Conformal Threshold: A threshold $\hat{q}_{ret}$ is calibrated on a held-out set to ensure that at least a $(1-\alpha_{ret})$ fraction of retrievable gold passages are retained, filtering out low-relevance noise at every turn.

C. Stage 2: Adaptive Early Stopping & Error Budget Allocation

This is the core innovation. Instead of using a single global error budget, MiCP allocates the error budget $\alpha$ across turns.

• Uncertainty Signal: Uses Normalized Entropy (NE) of the sampled answer distribution. Low NE indicates high confidence (samples cluster around one answer); high NE indicates uncertainty.
• Budget Decomposition: The total error budget $\alpha$ is decomposed into per-turn budgets $\alpha_t$.
  • Easy questions (answered early) consume less budget.
  • Harder questions (requiring more turns) reserve more budget.
  • The allocation accounts for the fraction of questions that are "answerable" at each turn vs. those that are unanswerable.
• Stopping Rule: At each turn $t$, the model computes the NE. If the score falls below a turn-specific calibrated threshold $\hat{q}_t$, the model stops.
• Prediction Set Construction:
  • If stopped early ($t^* < T$): The prediction set is built from clusters of answers accumulated up to $t^*$.
  • If exhausted ($t^* = T$): The set includes all accumulated answers plus a "Can't Answer" label to maintain coverage guarantees for unanswerable questions.

D. Composite Evaluation Metric

The authors introduce a new metric $L$ to evaluate the trade-off between reliability and efficiency:
$$L = \gamma \cdot \bar{T} - \frac{\sum n_{corr}^t / c_{ans}^t}{\sum n_{wrong}^t / (1 - c_{ans}^t)}$$
This metric rewards stopping early on correct answers while penalizing incorrect stops on difficult questions, balancing the number of turns ($\bar{T}$) against accuracy.

3. Key Contributions

1. First Multi-Turn CP Framework: MiCP is the first method to apply Conformal Prediction to multi-turn reasoning pipelines, providing formal coverage guarantees for adaptive stopping.
2. Multi-Level Error Allocation: A novel strategy that distributes the error budget across turns, allowing the model to stop early on easy questions while reserving budget for difficult ones, all while maintaining end-to-end coverage.
3. Unified Pipeline: The framework jointly calibrates retrieval filtering, stopping decisions, and final prediction sets, supporting both Adaptive RAG and ReAct agents.
4. New Evaluation Metric: A composite metric that explicitly evaluates the trade-off between coverage validity and inference efficiency (turns/cost).

4. Experimental Results

The authors evaluated MiCP on five benchmarks (Natural Questions, TriviaQA, HotpotQA, MuSiQue, 2WikiMultiHopQA) using three LLMs (Gemma-2-9B-IT, Qwen3.5-9B, GPT-4o-mini) in both Adaptive RAG and ReAct settings.

• Coverage Guarantees (RQ1):
  • MiCP successfully maintained the target coverage rate ($1-\alpha$) for both retrieval filtering (gold retention) and final prediction sets across all datasets and models.
  • The empirical coverage consistently met or exceeded the theoretical guarantee, even with early stopping enabled.
• Efficiency Gains (RQ2):
  • Reduced Turns: MiCP significantly reduced the average number of turns compared to the "No Early Stop" baseline (which runs all $T$ turns). For example, on 2WikiMultiHopQA, turns were reduced from 3.0 to ~1.7–2.5 depending on the model.
  • Smaller Prediction Sets: By filtering out noisy answers from unnecessary late turns, the size of the prediction set was reduced.
  • Model Performance: Newer models (Qwen3.5, GPT-4o-mini) showed greater efficiency gains, as they could better distinguish answerable vs. unanswerable questions.
• Optimization (RQ3):
  • Grid search optimization of the error budget allocation ($\alpha_t$) successfully improved the composite objective $L$, yielding more rational stopping decisions compared to uniform allocation.

5. Significance

This work addresses a critical bottleneck in deploying LLM agents for high-stakes domains (finance, healthcare) where reliability is paramount.

• Safety: It provides the first formal mathematical guarantee that an adaptive multi-turn system will not "give up" on a correct answer or hallucinate a wrong one without a safety net ("Can't Answer").
• Cost-Efficiency: It enables systems to stop reasoning as soon as sufficient confidence is reached, drastically reducing inference costs and latency without sacrificing accuracy.
• Generalizability: The framework is applicable to any multi-turn reasoning paradigm (RAG, ReAct, Tool Use), making it a foundational step toward reliable, autonomous AI agents.