- 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 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 is denoted 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 where is a gap parameter, and Theorem 2 establishes a worst-case regret. An instance dependent and minimax lower bounds (Theorem 3 and 4) show that these are essentially optimal.
Critical strengths
-
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.
-
The choice of pessimism-based policy is well justified and nicely explained.
Critical weaknesses
-
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.
-
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 Bernoulli random variables (e.g., in the experiments).
-
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
-
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.
-
The empirical counts may not be monotonic in the confidence level . Shouldn't this assumption be taken into account? Otherwise, the levels are not really ordered.
5 comments
Response to reviewer EKZZ (2/2)
4. Non-monotonicity
Our results do not require the conditional accuracies to be monotone in the confidence level, as we state in Appendix D.1. Therefore, non-monotonicity of the estimates is not a problem. The confidence levels themselves are ordered by construction (a higher 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 and 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.
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 of self-confidence levels and expert labels, we may form the conditional accuracy estimates hj,Nj,T1+1:=Nj,T1+11∑t=1T11Jt=jYt with Nj,T1+1:=∑t=1T11Jt=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 h and ω by their empirical averages using the offline samples and keeps them fixed during deployment. This h 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 N offline labeled samples with (ce,cexp,chold)=(1,0.25,0.03), μ=0.35.
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.