acceptodds
Under review as a conference paper at ICLR 2027

To Defer or Not to Defer? Online Learning with LLMs and Congested Experts

Abstract

Modern AI systems increasingly combine large language models (LLMs) with human experts, using the LLM to handle routine queries while deferring uncertain cases for expert review. When expert capacity is limited, however, deferral decisions must account not only for the reliability of the LLM but also for congestion in the expert queue. We formulate this as an online sequential decision-making problem in which, for each query, the system observes the confidence signal of the LLM's answer and must decide whether to output the answer or defer the query to a capacity-constrained expert. The reliability of the confidence signal is initially unknown and must be learned from expert feedback, which is both selectively observed (only deferred queries are labeled) and delayed by queuing. We propose KL-PBD, a learning algorithm that uses Kullback–Leibler lower confidence bounds on the unknown reliability parameters to guide deferral decisions. For confidence levels and horizon , KL-PBD achieves gap-dependent regret when the accuracy at every confidence level is bounded away from the deferral boundary, and worst-case regret. We establish matching lower bounds, showing that these rates are optimal up to logarithmic factors. Finally, we validate our approach on synthetic instances and real-world question-answering datasets, namely GSM8K, NuminaMath, and MedMCQA, using Qwen LLMs.

Primary area:
reinforcement learning
Keywords:
Learning to Defer, Large Language Models, Online Learning, Selective Feedback, Queueing, Regret Analysis

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_EKZZOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers the setting in which an LLM is used for making predictions and also provides an confidence level from one of KK levels. A decision maker then either accepts the prediction as is, or sends it an expert, who provide the correct answer. A prediction error incurs a cost, and deferring the query also incurs a cost, in the form both the cost of using an expert, as well as the cost of storing the query in a queue. The setup is formalized as a Markov decision process, in which the state is the number of queries in the queue. The probability that the LLM is correct given it is confident at some level 1≤j≤K1\leq j\leq K is denoted hjh_j called the conditional accuracy.

An initial result, Lemma 1, shows that for known conditional accuracy, the optimal deferral policy is such that if the conditional accuracy at the current time point is larger than a threshold (determined by the queuing and expert costs). The rest of the paper focuses on the case of unknown conditional accuracy, which involves both selective (ground truth is only revealed after deferral) and delayed feedback (it takes a few rounds for the expert to process the query).

An algorithm (KL_PBD) is proposed for regret minimization, which is based on playing according to the most pessimistic conditional accuracy vector that statistically agrees with the reward observations up to this round. Theorem 1 establishes a regret of O(Klog⁡Tγ)O(\frac{K\log T}{\gamma}) where γ\gamma is a gap parameter, and Theorem 2 establishes a O~(KT)\tilde{O}(\sqrt{KT}) worst-case regret. An instance dependent and minimax lower bounds (Theorem 3 and 4) show that these are essentially optimal.

Critical strengths
  1. The paper is comprehensive, and includes both gap dependent and worst-case regret for the KL-PBD algorithm (Theorems 1 and 2), as well as instance dependent and minimax lower bounds (Theorems 3 and 4). Additional extensions, e.g., to unknown confidence levels and service capacity distributions, are discussed in the appendix.

  2. The choice of pessimism-based policy is well justified and nicely explained.

Critical weaknesses
  1. The studied setting does not really has anything to do with LLMs, but is rather a general question of using agents to complete tasks (the agent is more costly, but provide accurate answers). Lemma 1 shows that the optimal policy boils down to a simple thresholding (send the task to an expert if the value of this action is larger than the value of solving it yourself). It is difficult to believe that a general setting of this form was not studied in the vast MDP/RL literature.

  2. Assumptions: The chose of an online setting is contrived. Unlike a bandit setting, these LLMs operate on existing systems that already operate for a long time (say, in the examples of the paper customer support, healthcare). The output of the LLM can be inspected on existing historical data (or using the experts offline), and from there very little exploration is needed. This just KK Bernoulli random variables (e.g., K=21K=21 in the experiments).

  3. The conditional accuracy vector is supposed to represent increasing confidence level, but this is not used by the algorithm. The policy deciding on the deferral is also agnostic to the features, and rely on the self-assessment of the LLM.

Questions for authors
  1. Why the cost of storing the query in the queue? This seems to be negligible compared to the cost of an expert or an erroneous decision.

  2. The empirical counts h^j,n\hat{h}_{j,n} may not be monotonic in the confidence level jj. Shouldn't this assumption be taken into account? Otherwise, the KK levels are not really ordered.

5 comments
AuthorsOpenReview ↗

Response to reviewer EKZZ (1/2)

We thank you for recognizing the paper’s thoroughness and clarity. Below, we address the concerns you raised.

1. Connection to LLMs and the MDP/RL literature

Our theoretical formulation is deliberately general, allowing different confidence signals and applications beyond LLMs. We consider this generality a strength rather than a limitation. Nevertheless, our work is directly motivated by LLM-based question answering, and our experiments use real LLM outputs.

As you noted, the optimal policy has a structure similar to optimal threshold policies in RL. However, to the best of our knowledge, existing related work differs in what is assumed known and in the feedback available for learning: for example, [1] assumes known rewards and learns unknown transitions from the next state observed after each action, while [2] assumes known rewards and service rates and learns arrival rates from all arrivals, regardless of admission decisions. In our setting, the reward is unknown, and the feedback to learn that reward is both selective and delayed. Thus, the similar threshold structure does not make these learning problems equivalent. See Appendix D.5 for a more precise comparison with these papers.

2. Online setting and offline calibration

Although our method does not require offline data to be available, in practice we may first perform an offline calibration phase to obtain initial estimates of the conditional accuracies using expert-labeled data, and then refine these estimates online. Specifically, given a dataset (Jt,Yt)t≤T1(J_t,Y_t)_{t \le T_1} of self-confidence levels and expert labels, we may form the conditional accuracy estimates h^j,Nj,T1+1:=1Nj,T1+1∑t=1T11Jt=jYt\widehat h_{j,N_{j,T_1+1}}:=\frac{1}{N_{j,T_1+1}}\sum_{t=1}^{T_1}\mathbf 1\\{J_t=j\\}Y_t with Nj,T1+1:=∑t=1T11Jt=jN_{j,T_1+1}:=\sum_{t=1}^{T_1}\mathbf 1\\{J_t=j\\}, compute the corresponding KL lower confidence bounds, and continue updating these counts and estimates with online expert reviews.

This warm-start setting is easier than the cold-start setting analyzed in the paper, and our regret guarantees continue to hold, with minor adjustments to account for the initial counts. Continuing to update the estimates online after the offline phase comes at little additional cost, since the computational cost of the algorithm is typically small compared to that of LLM generations and expert reviews. We compare with an offline-only baseline, which estimates hh and ω\omega by their empirical averages using the offline samples and keeps them fixed during deployment. This hh estimate coincides with KL-PBD+’s lower confidence bound in the first round of the online phase. The table below reports mean regret and 95% confidence intervals during the online phase over 20 runs for Qwen3-4B, using NN offline labeled samples with (ce,cexp,chold)=(1,0.25,0.03)(c_e,c_{\rm exp},c_{\rm hold})=(1,0.25,0.03), μ=0.35\mu=0.35.

DatasetMethodN=0N=0N=50N=50N=200N=200N=1000N=1000
GSM8KKL-PBD98.5 ± 7.886.1 ± 7.882.9 ± 8.480.1 ± 9.3
KL-PBD+33.9 ± 4.725.2 ± 4.032.2 ± 10.618.4 ± 4.4
Offline-Only—257.1 ± 74.5216.7 ± 72.7181.5 ± 50.6
NBD256.2 ± 2.5———
NuminaMathKL-PBD417.8 ± 15.7402.8 ± 14.6392.3 ± 15.0366.8 ± 14.7
KL-PBD+105.7 ± 10.3105.3 ± 14.485.2 ± 12.374.0 ± 9.3
Offline-Only—1816.7 ± 282.5880.5 ± 175.7336.2 ± 46.8
NBD232.1 ± 2.3———
MedMCQAKL-PBD101.0 ± 6.691.9 ± 7.666.9 ± 6.956.0 ± 4.9
KL-PBD+44.5 ± 5.839.2 ± 6.723.6 ± 5.518.1 ± 4.4
Offline-Only—1348.1 ± 185.6962.2 ± 181.1213.6 ± 50.2
NBD2579.9 ± 8.9———

KL-PBD+ achieves much lower regret than the offline only baseline, which highlights the benefit of continued learning.

3. Confidence signals and query information

We emphasize that our policy is not agnostic to the features, since the confidence signal is a function of the query and the LLM answer. We discuss the motivation for this representation in the first paragraph of our response to Reviewer wB5G.

We also clarify that the confidence signal used in our experiments is not based on a self-assessment of the LLM. We use the self-consistency score, which is the fraction of LLM answers to the same query that agree with the most frequent answer, and keep the most frequent answer as the final prediction. This approach is a well-established technique in NLP that both improves answer quality and provides an informative uncertainty signal [3,4]. More generally, our method can accommodate any scalar confidence signal, as we discuss in Appendix D.1.

AuthorsOpenReview ↗

Response to reviewer EKZZ (2/2)

4. Non-monotonicity

Our results do not require the conditional accuracies hj⋆h_j^\star to be monotone in the confidence level, as we state in Appendix D.1. Therefore, non-monotonicity of the estimates h^j,n\widehat h_{j,n} is not a problem. The confidence levels themselves are ordered by construction (a higher JtJ_t means higher confidence: for self-consistency this means that the majority-voted answer appears more frequently among the LLM-generated answers), but higher confidence does not necessarily mean higher accuracy, as illustrated in Figure 2.

5. Holding cost

The holding cost represents the impact of delayed answers per time slot, such as user dissatisfaction, rather than the cost of storing queries. While this cost may be small relative to the cost of an incorrect answer, it can accumulate over prolonged delays. We investigate its impact in Appendix G.2 (Table 4 and Figure 10).

6. References

[1] Arghyadip Roy, Vivek Borkar, Abhay Karandikar, and Prasanna Chaporkar. Online reinforcement learning of optimal threshold policies for Markov decision processes. IEEE Transactions on Automatic Control, 67(7):3722–3729, 2021.

[2] Lucas Weber, Ana Busic, and Jiamin Zhu. Reinforcement learning and regret bounds for admission control. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 52403–52427. PMLR, 21–27 Jul 2024.

[3] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. ICLR, 2023.

[4] Ante Wang, Linfeng Song, Ye Tian, Baolin Peng, Lifeng Jin, Haitao Mi, Jinsong Su, and Dong Yu. Self-consistency boosts calibration for math reasoning. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 6023–6029, Miami, Florida, USA, November 2024. Association for Computational Linguistics. doi: 10.18653/v1/2024.findings-emnlp.349.

1. Connection to LLMs and the MDP/RL literature + 5. Holding cost

I am not very familiar with this RL literature, but I would be very surprised if results for this setup cannot be deduced from more general models. As I mentioned, I also find the queueing aspect rather contrived for LLMs.
If at all, as you have mentioned in point #5, I would take the cost to be proportional to the processing time of the LLM, which depends on the query or its thinking effort more than anything else. However, I am not sure why this is model as a queue, and in this case, the MDP formulation is vacuous. You mention that the "theoretical formulation is deliberately general" yet LLM is highlighted in the title.

2. Online setting and offline calibration

What are the cost parameters choldc_{hold} and cexpc_{exp} associated with this table? The differences between offline algorithms -- that is, algorithms which commit to a specific policy, and online algorithms, is well established, and your table demonstrates it. If you continue for a large number of rounds, then the offline algorithm will get stuck on some specific value, whereas the no-regret online algorithm will converge to zero. However, given a large historical data, the difference the offline value could be sufficiently small. This strongly depends on the way the cost is measured.

3. Confidence signals and query information

Accepted. Thanks.

4. Non-monotonicity

Therefore in your model, the policy is solely based on self-assessment of the LLM, which could be wrong. Such an LLM is poorly calibrated, and I would assume otherwise, but your model can also be acceptable.

Thank you for your clarifications.

Reviewer_qnjyOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies online decision-making in LLM–expert collaboration: for each input, the system decides whether to accept the LLM’s answer or defer it to a human expert. Limited expert capacity makes continuous deferral cause queueing congestion and thus processing and waiting costs. Since the LLM’s true accuracy is unknown and true labels are available only for deferred questions reviewed by experts, feedback is selective and delayed.

The authors model the problem as a finite-horizon MDP with finite queue capacity and propose KL-PBD (KL-Pessimistic Bellman Deferral). It uses KL-based lower confidence bounds on accuracy across LLM confidence levels and computes the marginal cost of deferral via a Bellman value function, jointly handling online learning, information acquisition, and queue control. The paper provides gap-dependent and worst-case regret upper bounds, along with instance-dependent and minimax lower bounds, showing near-optimality. Experiments on GSM8K, NuminaMath-TIR, and MedMCQA with Qwen-series models, compared with learning-based and non-learning baselines, show clear benefits of using queue state and pessimistic estimation under limited expert capacity, delayed feedback, and poor confidence calibration. Overall, the paper integrates LLM confidence learning, selective feedback, and congested queue control into a unified online decision framework with clear theoretical and practical motivation.

Critical strengths
  1. The problem formulation is both novel and practically significant, extending delayed decision-making beyond the traditional prediction-and-deferral framework to a unified learning and control problem that jointly accounts for congestion costs, selective feedback, and delayed feedback. The paper clearly establishes the three interconnected roles played by deferral decisions: predictive decision-making, information acquisition, and queue control. Instead of treating LLM reliability estimation and deferral to experts as independent components, the paper explicitly captures their intricate coupling across three dimensions: predictive risk, since accepting incorrect LLM responses incurs direct losses; information acquisition, since deferring queries to experts yields ground-truth labels that improve subsequent reliability estimation; and queue congestion, since deferred queries consume limited expert capacity and increase the waiting costs of subsequent queries. This interdependence distinguishes the proposed problem from conventional offline Learning to Defer and standard selective classification. In particular, exploration itself consumes the scarce resources that the system must manage, making the joint optimization of online learning and queue control a valuable and promising research direction.

  2. The theoretical analysis in this work is relatively comprehensive: it not only analyzes the regret upper bound but also provides lower-bound analysis and worst-case analysis.

Critical weaknesses
  1. The experiments are essentially offline simulations rather than online deployments. Evaluations on real datasets (GSM8K, NuminaMath, and MedMCQA) are conducted as offline replays, using offline corpora to simulate selective and delayed feedback. This leaves a gap relative to online learning, and the feedback timing and congestion dynamics in the simulation are artificially constructed and may not reflect the congestion and delay distributions of real deployment. Although the experiments use real question-answering datasets and LLM outputs, query arrivals, the expert service process, and the feedback mechanism are mainly simulated according to pre-specified statistical models. This helps control variables and validate the algorithm, but it cannot fully reflect a real human–AI collaborative system.

  2. The paper uses self-consistency to construct confidence signals and discretizes them into KK levels: in the experiments, 20 generations are used to form confidence scores and K=21K=21 levels, and conditional accuracy is then estimated separately for each level. This design facilitates theoretical analysis but has limitations: per-level estimation can cause data sparsity, the statistical correlation between adjacent confidence levels is not explicitly exploited, and when confidence is continuous or when features such as question type, context, and task difficulty must be incorporated, the grouped model cannot fully exploit such information.

Questions for authors
  1. The analysis assumes a stationary confidence-level distribution and stationary conditional accuracies, with the confidence level and correctness label following an i.i.d. model; in practical LLM deployments, however, query distributions and model reliability may change over time. This raises the question of whether KL-PBD can be extended to non-stationary settings in which the conditional accuracy at each confidence level changes over time and, if not, how sensitive its empirical performance is to distribution shifts.
4 comments
AuthorsOpenReview ↗

Response to reviewer qnjy (1/2)

We thank you for recognizing the paper’s significance and thoroughness. Below, we address the concerns you raised.

1. Online evaluation and simulated expert dynamics

We first clarify that although our experiments use queries and answers collected offline, the learning and deferral decisions are made online. Collecting them in advance does not affect the learning process, since our problem is to decide whether to defer the query, not which queries or answers are generated. We indeed simulate query arrivals and expert service: this follows the evaluation approaches of related work in learning to defer in congested systems [1] and admission control [2,3].

2. Choice and use of confidence signals

Confidence signals and query features. You mention incorporating query features such as question type or task difficulty. In this work, we deliberately focus on confidence signals as informative low-dimensional summaries of the LLM’s reliability. This is motivated by their use in NLP to guide decisions about model predictions. The self-consistency signal used in our experiments is the fraction of sampled answers agreeing with the most frequent answer. Self-consistency improves answer accuracy via majority voting [4], while agreement between answers provides an informative, query-dependent confidence signal [5,6]. Incorporating additional features could improve this summary, but would require learning a model with greater statistical complexity. We discuss these points in more detail in the first paragraph of our response to Reviewer wB5G.

Discretization and data sparsity. To clarify, the self-consistency signal used in our experiments is already discrete. Discretization is needed if the chosen confidence signal is continuous or takes a large number of distinct values. The number of levels KK may then be chosen to trade off between modeling accuracy and statistical complexity: choosing KK optimally is an interesting question that we leave for future work. Regarding data sparsity, we point out that confidence levels that are rarely encountered have a small impact on our regret objective (achieving low regret does not require estimating every conditional accuracy with the same precision).

Sharing information across confidence levels. We estimate conditional accuracies separately so that our guarantees hold without structural assumptions. Our method can nevertheless be adapted to leverage structure. For example, if the conditional accuracy is Lipschitz in the self-confidence score, i.e., ∣hj⋆−hk⋆∣≤L∣pj−pk∣|h_j^\star-h_k^\star|\le L|p_j-p_k| for a known LL, we may replace the lower confidence bounds h‾j,t\underline h_{j,t} in Algorithm 1 by h‾j,tL:=max⁡k∈[K]h‾k,t−L∣pj−pk∣\underline h^L_{j,t}:=\max_{k\in[K]}\\{\underline h_{k,t}-L|p_j-p_k|\\}. Since h‾tL≥h‾t\underline h^L_t\ge\underline h_t and h‾tL\underline h^L_t remains a lower bound on h⋆h^\star whenever the confidence bounds hold, our regret guarantees still hold. In the datasets considered in our experiments, LL is typically fairly large, so leveraging the Lipschitz structure does not meaningfully improve regret, as summarized in the table below. The suffix -L denotes the Lipschitz modification. LL is chosen as the smallest possible Lipschitz constant given the dataset (T=105T=10^5, (ce,cexp,chold)=(1,0.25,0.03)(c_e,c_{\rm exp},c_{\rm hold})=(1,0.25,0.03), μ=0.35\mu=0.35, 100 runs, mean regret with 95% confidence intervals).

Model / datasetLLKL-PBDKL-PBD-LKL-PBD+KL-PBD+-L
Qwen2.5-0.5B GSM8K2.93314.1±6.3314.1 \pm 6.3313.2±6.3313.2 \pm 6.3116.0±3.8116.0 \pm 3.8111.2±4.2111.2 \pm 4.2
Qwen2.5-0.5B Numina2.46298.5±5.3298.5 \pm 5.3297.6±5.5297.6 \pm 5.5115.4±3.6115.4 \pm 3.6109.9±3.2109.9 \pm 3.2
Qwen3-0.6B Numina3.68451.9±7.3451.9 \pm 7.3457.6±8.3457.6 \pm 8.3159.4±5.0159.4 \pm 5.0152.4±4.9152.4 \pm 4.9
AuthorsOpenReview ↗

Response to reviewer qnjy (2/2)

3. Adaptation to nonstationary environments

As you noted, our analysis assumes i.i.d. observations. A natural way to adapt our algorithms to nonstationary settings is to use a sliding window to discard old observations, similarly to SW-UCB [7]. Given a window length WW, we estimate hj⋆h_j^\star using only the expert labels of queries that arrived in the last WW rounds. Writing Oj,tWO^W_{j,t} (resp. Nj,tWN^W_{j,t}) for the number of level-jj arrivals (resp. observed labels) in this window, we replace the KL-PBD confidence budget ϕ(T)\phi(T) by ϕ(W)\phi(W), and the KL-PBD+ confidence budget by log⁡(Oj,tW/Nj,tW)\log(O^W_{j,t}/N^W_{j,t}). We estimate ωj\omega_j by Oj,tW/min⁡(t,W)O^W_{j,t}/\min(t,W). The table below reports the mean regret and 95% confidence intervals over 24 runs on streams of T=105T=10^5 queries with (ce,cexp,chold)=(1,0.25,0.03)(c_e,c_{\rm exp},c_{\rm hold})=(1,0.25,0.03), μ=0.35\mu=0.35. Queries are sampled i.i.d. from one dataset up to round T/2T/2 and from another after round T/2T/2, so that both the confidence-level and accuracy distributions change at round T/2.T/2. Regret is measured against an oracle that also knows the change point. In practice, WW may be chosen carefully based on historical data. Here, we simply take WW to be 1010\\% and 2525\\% of the size of the full stream. The sliding-window appears particularly useful for KL-PBD+.

ModelStreamMethodNo windowW=104W=10^4W=2.5⋅104W=2.5\cdot10^4
Qwen3-4BGSM8K → MedMCQAKL-PBD341.7 ± 18.1427.3 ± 10.6299.4 ± 11.4
KL-PBD+200.8 ± 21.7176.5 ± 8.8118.8 ± 6.9
MedMCQA → GSM8KKL-PBD274.6 ± 6.5400.1 ± 9.1257.0 ± 6.8
KL-PBD+216.9 ± 6.2176.1 ± 6.0135.9 ± 6.3
Qwen3-0.6BGSM8K → MedMCQAKL-PBD889.4 ± 45.3856.1 ± 16.6761.7 ± 20.7
KL-PBD+993.7 ± 74.7458.4 ± 18.8502.1 ± 22.1
MedMCQA → GSM8KKL-PBD929.0 ± 17.7812.9 ± 13.4627.0 ± 12.2
KL-PBD+756.4 ± 24.4409.5 ± 7.8395.0 ± 10.8
Qwen2.5-0.5BGSM8K → MedMCQAKL-PBD2509.5 ± 190.1976.8 ± 11.5869.6 ± 46.3
KL-PBD+2367.3 ± 98.9525.3 ± 24.3605.5 ± 40.0
MedMCQA → GSM8KKL-PBD1516.0 ± 23.5987.7 ± 10.9847.0 ± 13.8
KL-PBD+1373.5 ± 29.1511.5 ± 11.7604.4 ± 13.1

4. References

[1] Thodoris Lykouris and Wentao Weng. Learning to defer in congested systems: The AI-human interplay, 2025.

[2] Lucas Weber, Ana Busic, and Jiamin Zhu. Reinforcement learning and regret bounds for admission control. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 52403–52427. PMLR, 21–27 Jul 2024.

[3] Arghyadip Roy, Vivek Borkar, Abhay Karandikar, and Prasanna Chaporkar. Online reinforcement learning of optimal threshold policies for Markov decision processes. IEEE Transactions on Automatic Control, 67(7):3722–3729, 2021.

[4] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. ICLR, 2023.

[5] Ante Wang, Linfeng Song, Ye Tian, Baolin Peng, Lifeng Jin, Haitao Mi, Jinsong Su, and Dong Yu. Self-consistency boosts calibration for math reasoning. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 6023–6029, Miami, Florida, USA, November 2024. Association for Computational Linguistics. doi: 10.18653/v1/2024.findings-emnlp.349.

[6] Murong Yue, Jie Zhao, Min Zhang, Liang Du, and Ziyu Yao. Large language model cascades with mixture of thought representations for cost-efficient reasoning. In B. Kim, Y. Yue, S. Chaudhuri, K. Fragkiadaki, M. Khan, and Y. Sun (eds.), International Conference on Learning Representations, volume 2024, pp. 21691–21728, 2024.

[7] Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In Proceedings of the 22nd International Conference on Algorithmic Learning Theory, pp. 174–188, Espoo, Finland, 2011. Springer-Verlag.

Thank you for the authors’ response. I have no further questions and will maintain my original score.

AuthorsOpenReview ↗

Response to Reviewer qnjy

We thank you for acknowledging our rebuttal and maintaining your positive assessment of the paper. We remain available to address any further questions.

Reviewer_wB5GOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper extends L2D to an online setting where human experts have limited capacity, meaning the system must account not only for whether the LLM is likely to be wrong, but also for the queue congestion created by sending another query for human review. Because the true reliability of the LLM's confidence score is unknown ahead of time and ground-truth labels are only revealed after a deferred query clears the expert queue, the system has to learn when to trust the LLM from selective, delayed feedback. The authors propose an algorithm that pairs pessimistic confidence bounds on the LLM's accuracy with dynamic programming over the queue, proving optimal regret bounds and evaluating the approach on math and medical QA benchmarks

Critical strengths

The math in the paper is impressive and very thorough. The authors provide matching gap-dependent and worst-case lower bounds, and even show the worst-case rate holds when the arrival and service rates have to be estimated on the fly. How they deal with the fact that plugging pessimistic accuracy estimates into the Bellman equation changes the queue threshold itself is nice, while also clearly showing in the experiments why greedy estimates get stuck when feedback is selective. Another part of me wonders how much AI could one-shot this, though...

Critical weaknesses
  • I believe the largest weakness is that the setup may be unrealistic and sample inefficient. This is because it completely ignores the actual question text and then treats ordered LLM confidence scores as isolated tabular bins that share 0 information with each other and have to be learned from scratch online. As every bin starts at zero with no offline calibration data or smoothness across adjacent confidence levels, the algorithm can burn through 10,000s of human reviews (and 20 LLM generations per query) just to learn a basic 1D accuracy curve. In fact, it seems that whenever the LLM's confidence scores are even halfway decent (like on GSM8K and NuminaMath), a simple non-learning baseline that just trusts the raw scores beats or ties their theoretical KL-PBD algorithm even after 100,000 queries.

  • The work feels somewhat incremental and might have limited practical impact, because it largely combines existing one-sided bandit confidence bounds with standard queue dynamic programming by stripping away all query context and treating ordered LLM confidence scores as independent tabular bins. In practice practitioners can easily calibrate a confidence curve on a small offline validation set rather than learning each bin from scratch over tens of thousands of online human-reviewed queries.

  • (minor) I am really not a fan of the title. I get that "To x or not to x?" is a quirky ML conference paper title, but it makes no sense in the context of the paper. The quote is from Hamlet contemplating suicide, which has zero relevance here beyond the fact that the decision is binary!

Questions for authors
  • Why is the theory not proved for KL-PBD+? In the experiments, KL-PBD+ is up to 4x better than KL-PBD (and standard KL-PBD actually loses to the non-learning NBD baseline on GSM8K and NuminaMath even after 100k queries). Does the KL-PBD+ confidence budget break the proof? or could your theorems be extended to cover it?

  • Is there a way to share information across adjacent confidence levels or warm-start from offline data? Treating the 21 confidence levels as totally separate bandit arms starting at zero takes tens of thousands of human reviews to learn. How easily could you incorporate basic smoothness across nearby bins or initialize from a small offline calibration set?

7 comments
AuthorsOpenReview ↗

Response to reviewer wB5G (1/3)

We thank you for your detailed review and appreciate your positive assessment of our mathematical analysis. Below, we answer your questions and address all concerns you raised.

1. Confidence signals provide informative summaries at manageable cost

We first emphasize that our approach does not ignore the query or the LLM’s answer. The confidence signal, which is inherently a function of both, provides an informative low-dimensional summary of the LLM’s reliability on a given query. It is well established in the NLP literature that confidence signals are useful summaries for guiding decisions [1,2,3,4]. In particular, [1, Section 3.5] report better accuracy-cost tradeoffs for cascades based on answer consistency than for alternatives that either fine-tune a text-based predictor offline or prompt an LLM to assess query difficulty or answer correctness. We similarly rely on informative confidence signals to reduce the learning problem to estimating accuracy as a function of confidence. This choice retains information about query difficulty and avoids the need to train an additional, higher-dimensional contextual model.

Cost of LLM generations. In our experiments, we use a sample-based confidence signal based on self-consistency, with 2020 generations per query. Importantly, these generations serve two purposes: they significantly improve the accuracy of the returned answer via majority voting [5], while their agreement provides an informative self-confidence signal [6, 1]. These generations can be parallelized, reducing their impact on latency. As described in Appendix D.1, our method can also use self-confidence scores that are not sample-based, such as scores based on token-level uncertainty, requiring only a single LLM generation per round.

2. The overhead in expert reviews due to learning is small

Please note that expert reviews serve two purposes:

  1. avoiding errors in the current round;
  2. learning the optimal deferral rule over time.

In particular, even the oracle, which follows the optimal deferral rule, must defer to the expert when the conditional accuracy of the observed confidence level is low. Therefore, we respectfully disagree that “the algorithm can burn through 10,000s of human reviews [...] just to learn a basic 1D accuracy curve”: most of these reviews are also requested by the oracle. The overhead in expert reviews due to learning, which we can measure by the excess number of reviews relative to the oracle, is comparatively small, as the table below highlights for the instances of Section 6 and Appendix H (T=105T=10^5, (ce,cexp,chold)=(1,0.25,0.03)(c_e,c_{\rm exp},c_{\rm hold})=(1,0.25,0.03), μ=0.35\mu=0.35, mean ±95\pm 95\\% confidence intervals over 100 runs). In a setting where expert reviews are particularly costly (i.e., cexpc_{\rm exp} is larger), our algorithms would defer even less.

ModelDatasetOracle reviewsExcess reviews (KL-PBD)Excess reviews (KL-PBD+)
Qwen3-4BGSM8K4,240791 ± 3242 ± 34
Numina17,2054,352 ± 58660 ± 75
MedMCQA23,0951,051 ± 38126 ± 29
Qwen3-0.6BGSM8K15,6283,417 ± 62850 ± 148
Numina28,3801,839 ± 46324 ± 70
MedMCQA32,430989 ± 39397 ± 74
Qwen2.5-0.5BGSM8K23,4533,417 ± 512,181 ± 120
Numina30,9661,796 ± 391,283 ± 62
MedMCQA34,735245 ± 3082 ± 32

3. Warm-starting after offline phase and leveraging structure between confidence levels

Warm-start. Our algorithm can directly leverage a warm-started estimate obtained from an offline phase.

Given a dataset (Jt,Yt)t≤T1(J_t,Y_t)_{t\le T_1} of self-confidence levels and expert labels, we may form the conditional accuracy estimates h^j,Nj,T1+1:=1Nj,T1+1∑t=1T11Jt=jYt\widehat h_{j,N_{j,T_1+1}}:=\frac{1}{N_{j,T_1+1}}\sum_{t=1}^{T_1}\mathbf 1\\{J_t=j\\}Y_t with Nj,T1+1:=∑t=1T11Jt=jN_{j,T_1+1}:=\sum_{t=1}^{T_1}\mathbf 1\\{J_t=j\\}, compute the corresponding KL lower confidence bounds, and continue updating these counts and estimates with online expert reviews.

This warm-start setting is easier than the cold-start setting analyzed in the paper, and our regret guarantees continue to hold, with minor adjustments to account for the initial counts. Continuing to update the estimates online after the offline phase comes at little additional cost, since the computational cost of the algorithm is typically small compared to that of LLM generations and expert reviews. We compare with an offline-only baseline, which estimates hh and ω\omega by their empirical averages using the offline samples and keeps them fixed during deployment. This hh estimate coincides with KL-PBD+’s lower confidence bound in the first round of the online phase. The table below reports mean regret and 95% confidence intervals during the online phase over 20 runs for Qwen3-4B, using NN offline labeled samples.

AuthorsOpenReview ↗

Response to reviewer wB5G (2/3)

DatasetMethodN=0N=0N=50N=50N=200N=200N=1000N=1000
GSM8KKL-PBD98.5 ± 7.886.1 ± 7.882.9 ± 8.480.1 ± 9.3
KL-PBD+33.9 ± 4.725.2 ± 4.032.2 ± 10.618.4 ± 4.4
Offline-Only—257.1 ± 74.5216.7 ± 72.7181.5 ± 50.6
NBD256.2 ± 2.5———
NuminaMathKL-PBD417.8 ± 15.7402.8 ± 14.6392.3 ± 15.0366.8 ± 14.7
KL-PBD+105.7 ± 10.3105.3 ± 14.485.2 ± 12.374.0 ± 9.3
Offline-Only—1816.7 ± 282.5880.5 ± 175.7336.2 ± 46.8
NBD232.1 ± 2.3———
MedMCQAKL-PBD101.0 ± 6.691.9 ± 7.666.9 ± 6.956.0 ± 4.9
KL-PBD+44.5 ± 5.839.2 ± 6.723.6 ± 5.518.1 ± 4.4
Offline-Only—1348.1 ± 185.6962.2 ± 181.1213.6 ± 50.2
NBD2579.9 ± 8.9———

((ce,cexp,chold)=(1,0.25,0.03)(c_e,c_{\rm exp},c_{\rm hold})=(1,0.25,0.03), μ=0.35\mu=0.35). KL-PBD+ achieves much lower regret than the offline only baseline, which highlights the benefit of continued learning. The excess reviews of our algorithms also decrease with the size of the offline dataset. For example, on Qwen3-4B/MedMCQA, N=1000N=1000 offline samples reduce KL-PBD+’s average excess online reviews from 126 to 48.

Sharing information across confidence levels. We deliberately treat self-confidence levels separately so that our guarantees hold without structural assumptions. Such assumptions may not hold in practice: for instance, in our experiments, the conditional accuracies are not monotone in the self-confidence score (Figure 2). Nevertheless, our method can be adapted to leverage structure. For instance, if the conditional accuracy is Lipschitz in the self-confidence score, i.e., ∣hj⋆−hk⋆∣≤L∣pj−pk∣|h_j^\star-h_k^\star|\le L|p_j-p_k| for a known LL, we may replace the lower confidence bounds h‾j,t\underline h_{j,t} in Algorithm 1 by h‾j,tL:=max⁡k∈[K]h‾k,t−L∣pj−pk∣\underline h^L_{j,t}:=\max_{k\in[K]}\\{\underline h_{k,t}-L|p_j-p_k|\\}. Since h‾tL≥h‾t\underline h^L_t\ge\underline h_t and h‾tL\underline h^L_t remains a lower bound on h⋆h^\star whenever the confidence bounds hold, our regret guarantees still hold. In the datasets considered in our experiments, LL is typically fairly large, so leveraging the Lipschitz structure does not meaningfully improve regret, as summarized in the table below. The suffix -L denotes the Lipschitz modification. LL is chosen as the smallest possible Lipschitz constant given the dataset (T=105T=10^5, (ce,cexp,chold)=(1,0.25,0.03)(c_e,c_{\rm exp},c_{\rm hold})=(1,0.25,0.03), μ=0.35\mu=0.35. 100 runs, mean regret with 95% confidence intervals).

Model / datasetLLKL-PBDKL-PBD-LKL-PBD+KL-PBD+-L
Qwen2.5-0.5B GSM8K2.93314.1±6.3314.1 \pm 6.3313.2±6.3313.2 \pm 6.3116.0±3.8116.0 \pm 3.8111.2±4.2111.2 \pm 4.2
Qwen2.5-0.5B Numina2.46298.5±5.3298.5 \pm 5.3297.6±5.5297.6 \pm 5.5115.4±3.6115.4 \pm 3.6109.9±3.2109.9 \pm 3.2
Qwen3-0.6B Numina3.68451.9±7.3451.9 \pm 7.3457.6±8.3457.6 \pm 8.3159.4±5.0159.4 \pm 5.0152.4±4.9152.4 \pm 4.9

4. KL-PBD+ analysis and comparison with NBD

Theoretical guarantees for KL-PBD+. In the immediate-service setting, the proof of Proposition 3 can be adapted to show that KL-PBD+ is also asymptotically optimal. There are two sources of regret to control: i) unnecessary deferrals when hj⋆>τh_j^\star > \tau; ii) incorrect acceptances when hj⋆<τh_j^\star < \tau. The analysis for (i) does not need modifications, since KL-PBD+ uses a smaller confidence budget than KL-PBD. For ii), the argument in the paper must be modified. It is sufficient to show that for each level jj with hj⋆<τh_j^\star < \tau, E[∑t=1T1Jt=j,At=0]=O(1).\mathbb{E}[\sum_{t=1}^T\mathbf1\\{J_t=j,A_t=0\\}]=O(1). We can use that if hj⋆<τh_j^\star < \tau and the learner accepts (At=0A_t=0), then h^j,n≥τ\widehat h_{j,n}\ge\tau and Oj,t≤nexp⁡n,kl(h^j,n,τ)O_{j,t}\le n\exp\\{n\\,\mathrm{kl}(\widehat h_{j,n},\tau)\\}, where n≥1n\ge1 is the number of observed labels. Adapting the argument leading to equation (5) in [8] then gives

\le\sum_{n\ge1}n(n+1)e^{-n\\,\mathrm{kl}(\tau,h_j^\star)} < \infty,$$ so the contribution of ii) is $O(1)$ (we can provide a detailed proof if needed). The rest of the proof is then the same as for KL-PBD. A finite-time analysis in the general setting is harder and beyond the scope of the paper. The main difficulty is that the uniform concentration bound of Lemma 8 no longer applies, which prevents the control of the regret due to concentration failure in Lemma 5. Even in the much simpler setting of profitable bandits, no regret bounds are known for the analogue KL-UCB+-4P [7].
AuthorsOpenReview ↗

Response to reviewer wB5G (3/3)

Comparison with NBD. A baseline that assumes perfect calibration such as NBD naturally performs well when the confidence scores happen to be well calibrated, but calibration is not guaranteed in advance and varies substantially across models and datasets; on MedMCQA, the NBD regret is 14 to 26 times the regret of KL-PBD. You mention that NBD beats or ties KL-PBD on GSM8K and NuminaMath. To clarify, this holds on three of the six GSM8K/NuminaMath instances, and is due to the conservative confidence budget required by the KL-PBD analysis. KL-PBD+ is specifically designed to alleviate this conservatism, and beats NBD on five of these six instances at T=105T=10^5, and on all six at T=2⋅105T=2\cdot10^5 (Tables 5 and 6).

5. Practical significance and technical novelty

Reviewer qnjy identifies our problem formulation as “both novel and practically significant”, in particular because we account for expert congestion. Calibrating a confidence curve on an offline validation set gives accuracy estimates, but does not address how to allocate limited expert capacity and account for the resulting delays. Our work addresses this joint learning and control problem.

Regarding the concern that our analysis "largely combines existing one-sided bandit confidence bounds with standard queue dynamic programming”, we believe this undersells the novelty of our analysis. We cannot rely on one-sided bandit confidence bounds alone, because KL-PBD is not exactly one-sided: since the pessimistic estimate h‾t\underline h_t enters the marginal cost of deferral Mth‾tM_t^{\underline h_t}, KL-PBD can accept queries that the oracle defers, without observing their labels. A key component of our analysis is Proposition 2, which allows us to relate the associated regret to the estimation error on deferred rounds.

6. Title

We do not mind changing the title, for instance to "Online Learning to Defer with LLMs and Congested Experts".

7. References

[1] Murong Yue, Jie Zhao, Min Zhang, Liang Du, and Ziyu Yao. Large language model cascades with mixture of thought representations for cost-efficient reasoning. In B. Kim, Y. Yue, S. Chaudhuri, K. Fragkiadaki, M. Khan, and Y. Sun (eds.), International Conference on Learning Representations, volume 2024, pp. 21691–21728, 2024.

[2] Lingjiao Chen, Matei Zaharia, and James Zou. FrugalGPT: How to use large language models while reducing cost and improving performance. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.

[3] Tal Schuster, Adam Fisch, Jai Gupta, Mostafa Dehghani, Dara Bahri, Vinh Tran, Yi Tay, and Donald Metzler. Confident Adaptive Language Modeling. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 17456–17472. Curran Associates, Inc., 2022. doi: 10.52202/068431-1269.

[4] Sungjae Lee, Hyejin Park, Jaechang Kim, and Jungseul Ok. Semantic Exploration with Adaptive Gating for Efficient Problem Solving with Language Models. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar (eds.), Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 588–606, Vienna, Austria, July 2025. Association for Computational Linguistics. doi: 10.18653/v1/2025.acl-long.29.

[5] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. ICLR, 2023.

[6] Ante Wang, Linfeng Song, Ye Tian, Baolin Peng, Lifeng Jin, Haitao Mi, Jinsong Su, and Dong Yu. Self-consistency boosts calibration for math reasoning. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 6023–6029, Miami, Florida, USA, November 2024. Association for Computational Linguistics. doi: 10.18653/v1/2024.findings-emnlp.349.

[7] Mastane Achab, Stephan Clémençon, and Aurélien Garivier. Profitable bandits. In Jun Zhu and Ichiro Takeuchi (eds.), Proceedings of The 10th Asian Conference on Machine Learning, volume 95 of Proceedings of Machine Learning Research, pp. 694–709. PMLR, 14–16 Nov 2018.

[8] Junya Honda. A note on KL-UCB+ policy for the stochastic bandit. arXiv preprint arXiv:1903.07839, 2019.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.