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

Vasileios Saketos; William Reveillard; Alexandre Proutiere; Sebastian Dalleiger; Ming Xiao

cs.LGOct 10, 2026

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

Authors: Vasileios Saketos, William Reveillard, Alexandre Proutiere, Sebastian Dalleiger, Ming Xiao

Organizations: KTH Royal Institute of Technology, Stockholm, Sweden

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 $K$ confidence levels and horizon $T$ , KL-PBD achieves $O(K\log T)$ gap-dependent regret when the accuracy at every confidence level is bounded away from the deferral boundary, and $\widetilde{O}(\sqrt{KT})$ 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.

Figures & tables

Panel of Figure 1 — Figure 1: Left: expert-aided LLM system with deferral policy $\pi$ and delayed feedback from completed expert reviews. Right: regret after $T=5\times 10^{4}$ queries on MedMCQA with Qwen3-4B against the expert service rate $\mu$ , comparing the queue-aware KL-PBD with the queue-unaware KL-UCB-4P . For $\mu=1$ , deferred queries are served before the next round and the queue does not build up, so queue awareness provides no benefit. For $\mu<1$ , deferred queries accumulate and create congestion, making queue-aware deferral essential for low regret. Details in Appendix H.3 .

Figure 2: Conditional accuracy of the self-consistency score (dashed line: perfect calibration).

Figure 3: Regret averaged over 100 runs. Curves leaving the frame are listed with their final regret.

Figure 4: Oracle thresholds for varying service rate

\mu

(top) and oracle decisions for

\mu=0.35

(bottom), for Qwen3-0.6B at round

t=T/2

Appendix figures & tables19 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Top: two-point instance with

\delta=0.08

. Bottom: monotone instance (dashed line: perfect calibration, i.e.,

h^{\star}_{j}=p_{j}

with

p_{j}=(j-1)/9

Figure 6: Conditional accuracy (top) and arrival rates (bottom) of the self-consistency score. The dashed line represents a perfectly calibrated score.

Figure 7: Regret of KL-PBD on the two-point instance for different

K

with

\delta=0.08

(left, shown up to

t=10^{5}

) and different

\delta

with

K=10

(center), and for different arrival distributions with

K=10

and

h^{\star}_{j}=0.5+\sqrt{\phi(T)/(2\omega_{j}T)}

(right).

95\%

confidence intervals over 100 runs are displayed as bands but are too small to be visible.

$K$	$\delta=0.02$	$\delta=0.04$	$\delta=0.06$	$\delta=0.08$	$\delta=0.10$	$\delta=0.15$
2	$334\pm 23$	$179\pm 13$	$121\pm 9$	$87\pm 7$	$71\pm 5$	$50\pm 3$
5	$1085\pm 51$	$555\pm 21$	$357\pm 13$	$267\pm 12$	$209\pm 9$	$138\pm 6$
10	$1592\pm 36$	$878\pm 28$	$589\pm 20$	$439\pm 13$	$353\pm 12$	$235\pm 7$
20	$1948\pm 11$	$1757\pm 44$	$1181\pm 29$	$889\pm 17$	$706\pm 15$	$462\pm 11$
50	$1997\pm 2$	$3564\pm 30$	$2966\pm 42$	$2225\pm 34$	$1789\pm 27$	$1168\pm 14$

Appendix

Table 1: Final regret

R_{T}

of KL-PBD at

T=2\cdot 10^{5}

for different

K

and

\delta

, mean

\pm

95% confidence interval half-width over 100 runs.

$\delta$	0.0025	0.005	0.01	0.015	$0.0192^{\dagger}$	0.025
$R_{T}$	$250\pm 0$	$500\pm 0$	$998\pm 3$	$1442\pm 16$	$1596\pm 32$	$1396\pm 43$
$\delta$	0.03	0.04	0.06	0.08	0.10	0.15
$R_{T}$	$1189\pm 41$	$878\pm 28$	$589\pm 20$	$439\pm 13$	$353\pm 12$	$235\pm 7$

Appendix

Table 2: Final regret

R_{T}

of KL-PBD at

T=2\cdot 10^{5}

for

K=10

and different

\delta

, mean

\pm

95% confidence interval half-width over 100 runs.

\dagger

\delta^{\star}=\sqrt{\phi(T)K/(2T)}\approx 0.019

Service rate $\mu$	Average queue size	Cumulative regret $R_{T}$	Response accuracy	Average threshold
0.20	$0.74\pm 0.01$	$194.06\pm 14.96$	$0.7710\pm 0.0010$	$0.2663\pm 0.0024$
0.40	$0.70\pm 0.01$	$233.59\pm 30.80$	$0.8445\pm 0.0008$	$0.5130\pm 0.0030$
0.50	$0.74\pm 0.00$	$115.49\pm 7.42$	$0.8856\pm 0.0005$	$0.5716\pm 0.0013$
0.60	$0.55\pm 0.01$	$135.36\pm 11.75$	$0.9070\pm 0.0006$	$0.6579\pm 0.0018$
0.80	$0.37\pm 0.00$	$301.17\pm 19.26$	$0.9603\pm 0.0011$	$0.7632\pm 0.0010$
1.00	$0.00\pm 0.00$	$80.61\pm 10.91$	$0.9937\pm 0.0001$	$0.8750\pm 0.0000$

Appendix

Table 3: Finite-horizon KL-PBD performance across service rates

\mu

with

\bar{B}=20

. Results are mean

\pm

95% confidence interval half-width over 20 runs.

Figure 8: KL-PBD threshold

\widehat{\tau}_{T/2}(b)

as a function of queue size

b

, averaged over the runs (left), and learned KL-PBD decisions, most frequent over the runs (right), at

t=T/2

for different service rates

\mu

$c_{\mathrm{hold}}$	$c_{\mathrm{exp}}$	Mean queue	Defer (%)	Accuracy (%)	Average threshold	Regret
0.005	0.25	$2.840\pm 0.057$	$49.62\pm 0.18$	$91.27\pm 0.11$	$0.635\pm 0.003$	$138.20\pm 8.81$
0.010	0.25	$2.106\pm 0.059$	$48.68\pm 0.29$	$90.87\pm 0.13$	$0.638\pm 0.005$	$183.55\pm 14.20$
0.050	0.25	$1.042\pm 0.027$	$45.20\pm 0.24$	$89.48\pm 0.12$	$0.604\pm 0.004$	$145.86\pm 18.98$
0.100	0.25	$0.751\pm 0.007$	$43.52\pm 0.17$	$88.56\pm 0.10$	$0.571\pm 0.003$	$118.58\pm 13.78$
0.500	0.25	$0.229\pm 0.005$	$22.90\pm 0.39$	$81.06\pm 0.11$	$0.429\pm 0.003$	$222.55\pm 33.59$
0.050	0.00	$1.221\pm 0.010$	$48.72\pm 0.18$	$89.97\pm 0.10$	$0.611\pm 0.003$	$71.57\pm 10.97$

Appendix

Table 4: KL-PBD performance across holding and expert-review costs with

\mu=0.5

. Results are mean

\pm

95% confidence interval half-width over 10 runs.

Figure 9: Effect of the expert-review cost on finite-horizon KL-PBD . We vary

c_{\mathrm{exp}}\in\{0,0.25,1,3\}

, with

T=50{,}000

\mu=0.5

\bar{B}=20

c_{e}=2

, and

c_{\mathrm{hold}}=0.05

. From the upper-left to the lower-right, the panels show accepted-LLM accuracy, cumulative regret, empirical deferral rate, cumulative completed expert labels, average queue size, and the deferral threshold

\widehat{\tau}_{T/2}(b)

t=T/2

as a function of queue size

b

Figure 10: Effect of the holding cost on KL-PBD . We vary

c_{\mathrm{hold}}\in\{0.005,0.01,0.05,0.1,0.5\}

with

T=50{,}000

\mu=0.5

\bar{B}=20

c_{e}=2

, and

c_{\mathrm{exp}}=0.25

\widehat{\tau}_{T/2}(b)

t=T/2

as a function of queue size

b

Figure 11: Learned KL-PBD decisions for varying

c_{\rm exp}

and

c_{\rm hold}

, for

t=T/2

(most frequent decision over the runs).

Model	Dataset	KL-PBD	KL-PBD+	GBD	SALMUT-SF	KL-UCB-4P	KL-UCB+-4P	NBD	FCT	FQT
Qwen3-4B	GSM8K	100.4 $\pm$ 3.3	35.4 $\pm$ 2.7	425.5 $\pm$ 20.5	531.0 $\pm$ 26.7	223.6 $\pm$ 5.9	71.3 $\pm$ 3.8	255.6 $\pm$ 1.3	756.3 $\pm$ 2.6	477.2 $\pm$ 1.9
Qwen3-4B	NuminaMath	424.4 $\pm$ 6.6	108.0 $\pm$ 4.2	1057.3 $\pm$ 82.0	1460.2 $\pm$ 41.0	7646.6 $\pm$ 101.8	4985.1 $\pm$ 156.7	231.9 $\pm$ 0.9	542.3 $\pm$ 1.2	195.4 $\pm$ 0.6
Qwen3-4B	MedMCQA	99.9 $\pm$ 2.9	40.2 $\pm$ 2.5	2236.7 $\pm$ 128.8	678.8 $\pm$ 13.8	7610.5 $\pm$ 191.7	5247.8 $\pm$ 87.7	2579.0 $\pm$ 4.0	5307.1 $\pm$ 5.4	4349.8 $\pm$ 5.3
Qwen3-0.6B	GSM8K	287.9 $\pm$ 7.0	93.5 $\pm$ 3.5	1468.3 $\pm$ 110.7	1173.0 $\pm$ 61.8	4654.6 $\pm$ 60.3	2227.5 $\pm$ 63.9	146.1 $\pm$ 2.6	2228.8 $\pm$ 3.8	185.5 $\pm$ 1.0
Qwen3-0.6B	NuminaMath	451.9 $\pm$ 7.3	159.4 $\pm$ 5.0	1264.1 $\pm$ 287.7	3007.0 $\pm$ 68.9	23600.1 $\pm$ 40.1	21539.7 $\pm$ 57.8	528.7 $\pm$ 1.3	8414.0 $\pm$ 27.7	1040.3 $\pm$ 2.3
Qwen3-0.6B	MedMCQA	106.0 $\pm$ 4.5	75.0 $\pm$ 5.8	2443.2 $\pm$ 218.0	306.0 $\pm$ 15.4	21834.8 $\pm$ 18.9	21831.9 $\pm$ 18.8	1501.1 $\pm$ 3.2	10439.5 $\pm$ 4.1	4070.2 $\pm$ 4.7

Appendix

Table 5: Final regret at

T=10^{5}

, mean

\pm

95% confidence half-width over 100 runs.

Figure 12: Regret of all algorithms, $T=10^{5}$ , 100 runs. Truncated curves are listed with their final regret.

Figure 13: Final regret versus horizon

T

, 24 runs per point. Truncated curves are listed with their final regret.

Model	Dataset	$T$	KL-PBD	KL-PBD+	GBD	SALMUT-SF	KL-UCB-4P	KL-UCB+-4P	NBD	FCT	FQT
Qwen3-4B	GSM8K	10k	43.4 $\pm$ 3.0	17.1 $\pm$ 1.8	39.9 $\pm$ 3.8	152.8 $\pm$ 5.5	97.6 $\pm$ 5.6	35.0 $\pm$ 3.9	26.4 $\pm$ 0.8	76.0 $\pm$ 1.6	48.9 $\pm$ 0.9
		50k	77.5 $\pm$ 4.8	28.7 $\pm$ 3.4	206.3 $\pm$ 20.2	357.4 $\pm$ 20.8	168.8 $\pm$ 10.8	60.4 $\pm$ 5.0	128.9 $\pm$ 1.9	379.2 $\pm$ 3.7	240.8 $\pm$ 2.9
		100k	98.2 $\pm$ 6.9	34.2 $\pm$ 4.3	414.6 $\pm$ 40.4	513.6 $\pm$ 33.7	221.6 $\pm$ 10.9	79.1 $\pm$ 6.7	255.7 $\pm$ 2.8	754.8 $\pm$ 4.1	478.5 $\pm$ 3.9
		200k	110.8 $\pm$ 9.6	38.3 $\pm$ 5.2	831.4 $\pm$ 81.0	746.8 $\pm$ 52.9	312.0 $\pm$ 8.9	99.4 $\pm$ 10.0	510.0 $\pm$ 3.3	1510.5 $\pm$ 5.7	954.4 $\pm$ 5.2
Qwen3-4B	NuminaMath	10k	130.4 $\pm$ 4.3	48.8 $\pm$ 3.5	108.0 $\pm$ 13.6	250.6 $\pm$ 18.7	1201.9 $\pm$ 25.1	560.0 $\pm$ 38.4	22.2 $\pm$ 0.8	53.7 $\pm$ 0.8	19.3 $\pm$ 0.4
		50k	314.2 $\pm$ 9.8	88.6 $\pm$ 7.5	530.3 $\pm$ 69.4	813.0 $\pm$ 63.7	4416.2 $\pm$ 167.6	2504.3 $\pm$ 183.6	115.2 $\pm$ 1.2	270.2 $\pm$ 1.9	97.0 $\pm$ 0.8

Appendix

Table 6: Final regret of the horizon sweep, mean

\pm

95% confidence half-width over 24 runs.

Figure 14: Service-rate sweep,

T=5\cdot 10^{4}

, 24 runs: final regret (left) and mean queue length (right).

Algorithm	$\mu=.2$	$\mu=.35$	$\mu=.5$	$\mu=.7$	$\mu=1$
KL-PBD	66.4 $\pm$ 3.9	83.5 $\pm$ 5.4	69.7 $\pm$ 7.0	80.9 $\pm$ 12.2	113.0 $\pm$ 17.2
KL-PBD+	36.2 $\pm$ 4.9	38.8 $\pm$ 4.5	31.2 $\pm$ 6.5	29.8 $\pm$ 6.4	41.9 $\pm$ 10.9
GBD	595.6 $\pm$ 57.9	1180.6 $\pm$ 123.7	1788.5 $\pm$ 207.5	2347.8 $\pm$ 249.4	2584.3 $\pm$ 259.7
SALMUT-SF	316.4 $\pm$ 13.8	407.1 $\pm$ 20.3	597.1 $\pm$ 58.6	528.1 $\pm$ 100.4	185.4 $\pm$ 148.1
KL-UCB-4P	10060.2 $\pm$ 228.5	5484.8 $\pm$ 371.2	2679.8 $\pm$ 302.3	1754.2 $\pm$ 252.2	158.2 $\pm$ 16.9
KL-UCB+-4P	8605.3 $\pm$ 110.2	3073.6 $\pm$ 185.5	584.5 $\pm$ 109.6	285.3 $\pm$ 50.8	41.9 $\pm$ 10.9

Appendix

Table 7: Final regret of the service-rate sweep, mean

\pm

95% confidence half-width over 24 runs.

Figure 15: Thresholds for varying

\mu

and decisions for

\mu=0.35

t=T/2

: KL-PBD for Qwen3-0.6B (top), oracle (middle) and KL-PBD (bottom) for Qwen3-4B, one run per

\mu

Figure 16: Final regret against average deferral rate, one point per run,

T=10^{5}

, and

\rho

the correlation for GBD .

Learning to Defer

Learning to defer trains AI systems to decide when to predict autonomously and when to route cases to human or machine experts.

See all 26 papers

May 12, 2026

Online Learning-to-Defer with Varying Experts

Learning-to-Defer (L2D) methods route each query either to a predictive model or to external experts. While existing work studies this problem in batch settings, real-world deployments require handling streaming data, changing expert availability, and shifting expert distribution. We introduce the first online L2D algorithm for multiclass classification with bandit feedback and a dynamically varying pool of experts. Our method achieves regret guarantees of

O((n+n_e)T^{2/3})

in general and

O((n+n_e)\sqrt{T})

under a low-noise condition, where

T

is the time horizon,

n

is the number of labels, and

n_e

is the number of distinct experts observed across rounds. The analysis builds on novel

\mathcal{H}

-consistency bounds for the online framework, combined with first-order methods for online convex optimization. Experiments on synthetic and real-world datasets demonstrate that our approach effectively extends standard Learning-to-Defer to settings with varying expert availability and reliability.

Dang Hoang Duy, Yannis Montreuil, Maxime Meyer +3

School of Computing, National University of Singapore, Singapore · IPAL, IRL 2955, Singapore · Department of Mathematics, National University of Singapore, Singapore, 117543 +2

Learning to Defer Bandit Learning Multiclass Classification Online Learning

Ask PDF

Sep 5, 2026

Online Learning with LLM Experts from Limited Feedback

We study adaptive routing of prompts to large language model (LLM) experts to maximize response quality in an online setting with limited feedback. We formulate it as a bandit problem with

K

actions that represent experts and

d

features that encode prompts, over a horizon of

T

rounds. We propose algorithms that strategically select and observe rewards to minimize regret. In the full-information setting, we achieve a regret of

\tilde{O}(d T / \sqrt{m})

, while in the bandit setting we achieve

\tilde{O}(d T \sqrt{K / m})

, where

m \ll T

is a budget on feedback. Our experiments show that we efficiently learn high-quality routing strategies across diverse LLMs from limited feedback.

Wang Wei, Soumyabrata Pal, Koyel Mukherjee +4

Virginia Tech · Adobe Research

LLM Routing Multi-Armed Bandits Linear Contextual Bandits

Ask PDF

Oct 5, 2026

A Query Is Not a Commitment: Learning to Correct Expert Answers in Online Deferral

An inaccurate expert can still provide useful information after correction. We study online learning to defer in which the learner chooses an expert and fixes a correction function before purchasing its answer, then applies that function to the answer received. The difficulty is that observed losses reflect both expert quality and an unfinished correction: early errors can discourage queries that would be valuable after learning. We propose ORUCB, which pools shared and expert-specific polynomial responses. A bound on cumulative response-learning error calibrates confidence-weighted risk regression and exploration, allowing the router to account for this error when deciding which answers to buy. Under bounded residuals and disagreements, a fixed feasible model of optimal responses, and linear models of free and optimal queried risk, the calibrated algorithm achieves high-probability pseudo-regret

O(\sqrt T\log(T+1))

over

T

rounds for fixed problem parameters. The guarantee permits singular answer distributions and misspecified shared responses; optimality is relative to the bounded response class. On four test streams, the selected cubic policy has lower fee-inclusive cost than seven baselines that deploy answers unchanged. Comparisons with a common correction learner examine routing, while six-price comparisons measure cost and query rates.

Yannis Montreuil, Axel Carlier, Lai Xing Ng +1

School of Computing, National University of Singapore · IRIT, Toulouse INP, France · Institute for Infocomm Research, A*STAR, Singapore

Cost-Sensitive Learning Learning to Defer

Ask PDF

Abstract

Learning to Defer

Explore similar work

Online Learning-to-Defer with Varying Experts

Online Learning with LLM Experts from Limited Feedback

A Query Is Not a Commitment: Learning to Correct Expert Answers in Online Deferral