PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Stopping for Multi-Turn LLM Reasoning

Xiaofan Zhou, Huy Nguyen, Bo Yu, Chenxi Liu, Lu Cheng

arXiv:2604.01413v3cs.CLcs.AI

TL;DR

Multi-turn LLM pipelines need to decide when to stop, but existing heuristics and single-shot conformal methods do not provide coverage guarantees across adaptive stopping. MiCP allocates error budgets across turns, and experiments report target coverage with fewer turns, lower inference cost, and smaller prediction sets; a new metric evaluates coverage validity alongside efficiency.

  • Problem

    Heuristic stopping rules and single-shot LLM conformal methods do not guarantee coverage for multi-turn pipelines that stop adaptively.

    Source: §1 · p. 2

  • Method

    MiCP allocates conformal error budgets across turns to support early stopping with an overall coverage guarantee, including in adaptive RAG and ReAct.

    Source: §1 · p. 2

  • Results

    Experiments report target coverage while reducing turns, inference cost, and prediction set size on single-hop and multi-hop QA tasks.

    Source: §1 · p. 3, §6 · p. 10

  • Takeaways & Limitations

    The proposed metric jointly evaluates coverage validity and efficiency, including the benefit of correct answers with fewer turns and penalties for unnecessary steps.

    Source: §4.4 · p. 7

Abstract

from arXiv · show

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: \textbf{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.

1 Introduction

Multi-turn LLMs need a principled stopping rule that balances insufficient evidence against the cost and possible errors of continuing. MiCP allocates conformal error across turns to support early stopping with an overall coverage guarantee, and experiments report efficiency gains while achieving target coverage.

1 Introduction

  • Stopping too early can yield incorrect answers, while excessive turns increase latency and computation cost and can introduce errors.Existing confidence thresholds, fixed retrieval budgets, and manual criteria offer no formal guarantee that the prediction contains the correct answer.Source: §1 · p. 2
  • Standard LLM conformal prediction applies only after a single-shot process, while adaptive pipelines need both a stopping decision and coverage across possible stopping times.Applying it independently at each turn does not guarantee overall coverage and can require combinatorially many sampled trajectories.Source: §1 · p. 2
  • MiCP allocates distinct error budgets across turns, enabling early stopping while maintaining an overall coverage guarantee in adaptive RAG and ReAct.It also supports rejection when a question remains too uncertain within the allowed computation budget.Source: §1 · p. 2
  • Experiments on adaptive RAG and ReAct report target coverage alongside fewer turns, lower inference cost, and smaller prediction sets on single-hop and multi-hop QA tasks.The paper also introduces an evaluation metric jointly reflecting coverage validity and efficiency.Source: §1 · p. 3

2 Related Work

Prior multi-turn LLM work uses diverse signals to decide whether and how to retrieve, while conformal methods for LLMs have focused on single-shot prediction or answer-set construction. MiCP extends conformal coverage to multi-turn interactions with early stopping.

2.1 Multi-turn LLMs

  • Adaptive RAG methods use signals such as reasoning sufficiency, learned retrieval decisions, token probabilities, attention, answer consistency, hidden states, or hallucination indicators to guide retrieval.The paper primarily evaluates MiCP in adaptive RAG and also tests ReAct for generalizability.Source: §2.1 · p. 3

2.2 CP for LLM

  • LLM conformal methods use sampled-answer frequencies, generalize or remove uncertain outputs, or abstain, but prior approaches do not address early stopping across multi-turn interactions.MiCP extends the “Can’t Answer” mechanism to multi-turn interactions while preserving the no-early-stop coverage guarantee.Source: §2.2 · p. 3

3 Preliminary

Split conformal prediction separates model training from calibration and constructs prediction sets from calibrated nonconformity scores. For LLMs, sampled responses can be clustered and their frequencies used to score and select answers.

Foundations of Split CP

  • Split CP is a post-hoc, distribution-free framework that separates model training from threshold calibration to construct prediction sets with finite-sample coverage guarantees.It does not require additional pretraining.Source: §3 · p. 4
  • A nonconformity score measures how unusual a label is for an input under a model, and calibration scores determine a threshold at the chosen error rate.The threshold is obtained as a quantile over calibration-set scores.Source: §3 · p. 4
  • For a new input, CP includes candidate labels whose nonconformity scores meet the calibrated threshold, yielding a prediction set with marginal coverage of at least 1 − α.CP also aims to keep prediction sets concise enough to be useful.Source: §3 · p. 4

CP for LLMs

  • For LLMs, sampled answers are clustered by semantic equivalence and cluster frequency supplies nonconformity scores for selecting prediction-set answers.Negative entropy and semantic similarity can help break ties when discrete frequency scores cause a concentration problem.Source: §3 · p. 4

4 Method

MiCP combines calibrated retrieval filtering, turn-specific stopping, and final prediction-set construction to support adaptive stopping with an overall coverage guarantee. Its method also introduces a composite metric for evaluating stopping-policy efficiency and answer quality.

4 Method

  • MiCP combines turn-level confidence estimation, adaptive early stopping, and final prediction-set construction, using turn-specific conformal thresholds and an optional “Can’t Answer” label.The framework covers adaptive RAG and ReAct pipelines.Source: §4 · pp. 4–5

4.1 Problem Setup and Notation

  • MiCP calibrates retrieval filtering and adaptive prediction-set stopping in two stages, with the final set designed to contain a sampled correct answer or abstain.At each turn, it filters passages using a relevance threshold calibrated to retain approximately 1 − αret of retrievable gold passages.Source: §4.1 · pp. 5–6

4.2 Retrieval Threshold Calibration

  • A gold passage’s optimistic relevance score is its maximum relevance across turns; a calibrated threshold retains relevant passages while filtering low-relevance evidence.The stated guarantee is that at least a 1 − αret fraction of retrievable gold passages are retained.Source: §4.2 · p. 6

4.3 Sequential NE Calibration with Error Budget Allocation

  • MiCP uses normalized entropy of sampled answers as an uncertainty signal and allocates the total error budget across turns to set turn-specific thresholds.The allocation accounts for questions whose gold answers have not appeared in samples by the current turn.Source: §4.3 · pp. 6–7

4.4 Composite Evaluation Metric

  • The composite metric balances average turns against answer quality, accounting for whether questions are answerable at each turn and penalizing incorrect answers when they remain unresolved.Its γ parameter controls the efficiency–quality trade-off, and the metric can evaluate stopping policies beyond MiCP.Source: §4.4 · p. 7

4.5 Final Answer Prediction Set Confidence Threshold Calibration

  • For calibration samples whose gold answers appear among sampled answers before stopping, MiCP scores gold-answer clusters across turns and calibrates a conformal threshold.Cluster confidence is based on sample frequency, optionally adjusted by normalized entropy.Source: §4.5 · p. 7

4.6 Prediction Set Construction

  • At test time, MiCP stops at the first turn when the highest-confidence cluster exceeds its threshold, returning accumulated high-confidence clusters or adding “Can’t Answer” after all turns.If no threshold is met, the model continues through all T turns.Source: §4.6 · pp. 7–8

5 Experiment

MiCP is evaluated on five single- and multi-hop QA benchmarks using adaptive RAG and ReAct, with tests of coverage, efficiency, and optimization. The reported results show coverage at or above the target and improved efficiency with early stopping.

5.1 Experimental Setup

  • The evaluation spans five single- and multi-hop QA benchmarks and tests MiCP on both adaptive RAG and ReAct.The experiments use three LLMs and 900 examples per dataset, split into optimization, calibration, and test sets.Source: §5.1 · p. 8
  • MiCP maintains prediction-set coverage at or above the 1 −α target across datasets and models, including with early stopping enabled.Retrieval gold-retention rates also closely track the target.Source: §5.1 · p. 9, Figure 3 · p. 9
  • MiCP improves inference efficiency by reducing average turns and consistently improves prediction efficiency by reducing prediction-set size.The authors attribute the latter to filtering answers from unnecessary late turns, which may add noisy or incorrect answers.Source: §5.1 · p. 9
  • Optimizing for average turns yields the fewest turns and smallest prediction sets among the reported MiCP variations.The authors explain that this objective encourages allocating more error budget to early turns and stopping sooner.Source: §5.1 · p. 10
  • Grid search over Qwen3.5-9B and gpt-4-mini optimizes the proposed objective, yielding more rational early-stopping decisions; MiCP variants consistently improve on baseline, with smaller but consistent gains on Gemma-2-9B-IT.On Gemma, avg-turn achieves the best objective performance without optimization. The authors suggest difficulty distinguishing answerable from unanswerable questions may make optimization unstable.Source: §5.1 · p. 10

6 Conclusion

The conclusion presents MiCP as a conformal framework for multi-turn LLM pipelines that jointly calibrates retrieval, stopping, and final prediction sets. Across five QA benchmarks, it reports target coverage at retrieval and answer stages alongside improved efficiency.

6 Conclusion

  • MiCP jointly calibrates retrieval filtering, adaptive early stopping, and final prediction-set construction while maintaining an overall 1 −α coverage guarantee.The framework is intended for multi-turn pipelines including adaptive RAG and ReAct.Source: §6 · p. 10
  • Across five single- and multi-hop QA benchmarks with three LLMs, MiCP achieves target coverage at retrieval and answer stages while reducing turns and retrieval cost.The conclusion also reports competitive prediction-set sizes.Source: §6 · p. 10

A.1 Experiment Setting

The experimental setting fixes retrieval, sampling, and optimization parameters for adaptive RAG and ReAct, and evaluates several target error rates over three random seeds.

A.1 Experiment Setting

  • The experiments use an Elasticsearch-based retriever over Wikipedia, returning the top 10 passages at each turn, with a maximum of 3 turns.They draw 15 stochastic answer samples per turn at temperature 1.4.Source: §A.1 · p. 13
  • Grid search uses 20 steps per dimension to optimize turn-specific error-budget allocation.Results are averaged over three random seeds for dataset splits.Source: §A.1 · p. 13
  • The target error rates are α ∈ {0.05, 0.10, 0.15, 0.20, 0.25}, with η = 0.1 and retrieval error budget αret = 0.1.Source: §A.1 · p. 13

A.2 Proof of Retrieval Calibration Coverage Guarantee

The proof uses exchangeability of calibration and test relevance scores to justify a conformal threshold for retrievable gold passages. It calibrates on retrievable, rather than all annotated, gold passages to avoid inflating the threshold with unretrievable ones.

A.2 Proof of Retrieval Calibration Coverage Guarantee

  • The proof treats the n calibration scores and a test score for a retrievable gold passage as exchangeable, then applies the split conformal prediction guarantee.The passage states the threshold uses the (n−1)α/n-quantile of calibration scores.Source: §A.2 · p. 13
  • The expected gold-retention guarantee follows because the marginal guarantee holds for each retrievable gold passage.Source: §A.2 · p. 14
  • Calibration uses retrievable gold passages rather than all annotated gold passages, avoiding threshold inflation from passages that cannot be retrieved.Source: §A.2 · p. 14

A.3 Proof of Prediction Set Coverage Guarantee

The proof establishes an overall 1−α prediction-set coverage guarantee by combining the answerable and unanswerable cases under exchangeability.

A.3 Proof of Prediction Set Coverage Guarantee

  • Per-turn thresholds for unanswerable questions use their turn-specific calibration subsets and error budgets to bound premature early stopping.If a question reaches the final turn, the “Can’t Answer” label is appended by construction.Source: §A.3 · pp. 14–15
  • The prediction set has at least 1−α coverage for an exchangeable test example, combining the answerable and unanswerable cases.The proof bounds each case by 1−α and combines them by total probability.Source: §A.3 · pp. 14–15
  • The guarantee is marginal over calibration and test-data randomness; subgroup-conditional coverage would require group-conditional calibration.The authors leave conditional coverage for specific subgroups to future work.Source: §A.3 · p. 15
Loading 2604.01413v3…