Cost-efficient Knowledge-based Question Answering with Large Language Models
Authors: Junnan Dong
Qinggang Zhang
Chuang Zhou
Hao Chen
Daochen Zha
Xiao Huang
Venue: NeurIPS 2024 poster (2024)
Keywords: Large Language Models
Knowledge-based Question Answering
Efficient Machine Learning
Primary area: natural_language_processing
TL;DR: This paper moves the Pareto frontier of both inferential accuracy and cost saving for knowledge-based question answering with large langue models.

Abstract: Knowledge-based question answering (KBQA) is widely used in many scenarios that necessitate domain knowledge. Large language models (LLMs) bring opportunities to KBQA, while their costs are significantly higher and absence of domain-specific knowledge during pre-training. We are motivated to combine LLMs and prior small models on knowledge graphs (KGMs) for both inferential accuracy and cost saving. However, it remains challenging since accuracy and cost are not readily combined in the optimization as two distinct metrics. It is also laborious for model selection since different models excel in diverse knowledge. To this end, we propose Coke, a novel cost-efficient strategy for KBQA with LLMs, modeled as a tailored multi-armed bandit problem to minimize calls to LLMs within limited budgets. We first formulate the accuracy expectation with a cluster-level Thompson Sampling for either KGMs or LLMs. A context-aware policy is optimized to further distinguish the expert model subject to the question semantics. The overall decision is bounded by the cost regret according to historical expenditure on failures. Extensive experiments showcase the superior performance of Coke, which moves the Pareto frontier with up to 20.89% saving of GPT-4 fees while achieving a 2.74% higher accuracy on the benchmark datasets.

Cost-efficient Knowledge-based Question Answering with Large Language Models
Junnan Dong', Qinggang Zhang', Chuang Zhou', Hao Chen
Daochen Zha?, Xiao Huang'
The Hong Kong Polytechnic University 2 Rice University
(hanson dong, qinggangg- zhang, chuang-qqzj wehouoeeooneeeeeee .wa.cctt..poo polyu. hk, sundaychenhao@gmail.. com, daochen zha@rice edu, xiaohuangdpolyu. edu. hk
Abstract
Knowledge-basee question answering (KBQA) is widely used in many scenar- ios that necessitate domain knowledge. Large language models (LLMs) bring opportunities to KBQA, while their costs are significantly higher and absence domain-specific knowledge during pre-training. We motivated to combine LLMs and prior small models on knowledge graphs (KGMs) for both inferential accuracy and cost saving. However, it remains challenging since accuracy and cost are not readily combined in the optimization as two distinct metrics. is also laborious for model selection since different models excel in diverse knowl- edge. To this end, we propose Coke, novel cost-efficient strategy for KBQA with LLMs, modeled as a tailored multi-armed bandit problem minimize calls LLMs within limited budgets. We first formulate the accuracy expectation with cluster-level Thompson Sampling for either KGMs or LLMs. context-aware policy is optimized to further distinguish the expert model subject to the question semantics. The overall decision bounded by the cost regrer according to historical expenditure on failures. Extensive experiments showcase the superior performance Coke, which moves Pareto frontier with up to 20.89% saving of GPT-4 fees while achieving 2.74% higher accuracy on the benchmark datasets.
1 Introduction
Knowledge-hon shaleeeee-eeedddddoee question answering (KBQA) has gained significant attention across various special- ized domains, e.g., education and medicine [24 13 21 20 Given question, the model is required to make inferences based necessary reasoning background [14]. Inspired by the effectiveness of knowledge graphs (KGs), e.g., ConceptNet [33 8) where real-world entities are represented in the structural form as (head entity, relation, tail entity) 77. KG-based models (KGMs) have been pro- posed to leverage KGs for reasoning. Based on the hypothesis that answers could be located multiple hops away from the question concepts [24 in KGs, former studies mainly dedicated to tracing the
trajectory from questions to answers to model the structural information [16] 25
5 or utilizing
graph neural networks (GNNs) to learn the question-specii
subgraph from KGs
14
37
39]
With the emergence of large language models (LLMss), e-g-, ChatGPT and GPT-4 29
They have
shown remarkable performance benefited from the injected knowledge during pre-training [8 12] However, it is challenging the open-source LLMs with cloud service is prohibitive [2] 9.. GPT-4 is estimated to cost at least thousands of dollars for pilot-scale customer service
adopt LLMSs in practice. First, either calling the API or deploying
6 while Llama3 70B requires unaffordable
Corresponding Author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Question Context Answer choices
50,00
Lanpugp Mark
GTT4
Open
MangA
72/075
$2OOK%
APS/Clont Service cor
Suti Goee:
Greasebi
$0.00%
guavall
71.15%
75
15.80%
Snall KG-based Models
LLMs
50,009
(N)
(b)
(c)
Figure I: A sketched overview of LLMs and small KGMs in (a) We visualize the Acc./Param size of both pipelines of models in (b) The overlaps among different model predictions are shown in (c).
computation resources for small business, c.g., 40G graphics memory, let alone the high throughput scenarios like online e-commerce [30]. Second, LLMs may struggle identify the correct answer for certain questions due to the lack of particular knowledge that is not covered in their pre-training They are considered unreliable to assist pedagogical or medical purposes since they could generate hallucination
corpus I 32 L5).
[3 18 and misleading responses 11 19].
We illustrate the sketched overview of LLMs and KGMs methods in Figure (a) where LLMs are used in a zero-shot setting with direct prompts, e.g.. [Question: Choi ces), and KGMs require the external domain KG as reasoning background. In Figure (b), we visualize the accuracy/parameter size of four types of models. In general, KGMs are far more lightweight considering model size but tend to underperform LLMs overall. Conversely, LLMs are more computationally expensive and may struggle with specific questions that demand knowledge not covered in the pre-training corpus. We are thereby motivated to combine the strengths of LLMs and KGMs through question-specific model selection to improve the Pareto frontier, achieving higher inferential accuracy and lower costs.
However, it is nontrivial for two major challenges. First, inferential accuracy and cost saving two distinct metrics. It is hard to combine them in the optimization simultaneously. Since more parameters will lead to higher costs, it indicates the importance of careful selection that balances both exploration and exploitation. Second, selecting the most suitable model for particular questions is laborious. In T (c). we showcase the overlaps among several representative models on the benchmark OpenBookQA (28) dataset. While different models focus on various considerations, they may consequently excel in diverse knowledge and question types. For example, HamQA [14] focuses on hypernymy in the questions, i.e., cats and mammals. This makes it expensive to incorporate expertise according to the specialty of models to answer diverse real-world domain-specific questions.
To this end, we present a novel cost-efficient strategy to leverage LLMs for KBQA, i.e., Coke. It is modeled as tailored multi-armer bandit (MAB) problem, which is trained to assign the most promising model for each question within a considerably limited budget. Specifically, we assemble two sets of base models, i.e., L.MSs and KGMs to balance both inferential accuracy and cost saving. (i) we first model the preliminary selection with a cluster-level Thompson Sampling. It suggests the accuracy expectation of choosing either LLMs KGMs based on historical success and failure at Beta distribution. (ii) A context-aware policy is learned to further distinguish the most suitable model. This could effectively assign the corresponding expert for the given question semantics. (fii The overall decision making is bounded by the cost regret. It indicatively constrains the selection based on the cumulative expenses incurred from fallures of the current model.
Contributions.
We formally define the task of optimizing both inferential accuracy and cost for KBQA with LLMs.
A novel cost-efficient strategy, Coke, is presented to automatically assign the most promising model for particular questions. It could effectively make reliable decisions considering both inferential accuracy and cost saving, making balance of exploration and exploitation during selections.
Extensive experiments over three domain-specific benchmark datasets demonstrate the superiority of our proposed framework, moving the Pareto frontier to achieve higher accuracy and lower costs.
2

---

2 Problem Formulation
2.1 Task Definition
We adopt lowercase alphabets for scalars (e.g., m), boldface lowercase letters for vectors(e.g.. q)
and boldface uppercase ones for matrices (e.g.. Q). The decorated letters are used for sets, e.g., A. We assemble two clusters of models, i.e., C = {CL, Ck } for sets of LLMs and KGMs, respectively. All the candidate models in C are denoted as MM = { [m1, my }- The knowledge graph used in KGMs is expressed as G where real world entities are represented in the form of triples as (e,, ex).
Given domain-specific questions Q = {ei, 92. and several candidate models M, we aim to optimize the framework to identify the most promising model within a limited budget to invoke LLMs. The overall performance is evaluated by both inferential accuracy and cost saving, We aim to maximize the accuracy comparing prediction i and ground truth y/, i... mar (face (ye Bt)), and minimize the costs, i.e., min(Senst (p(m))(:) where p(m) is the unit cost of model m..
2.2 Performance Evaluation
For fair comparisons, we divide the overall evaluation Coke against state-of-the-arr baselines into two parts considering both inference accuracy and cost saving.
Inferential accuracy: The performance of KBQA task itself is evaluated by the overall accu- racy of the model prediction compared with ground truths, i.e., [0, 1] for each question indicates wrong/correct. The accuracy expected to be as high as possible to correctly answer more questions.
The cost of using particular models often case by case. It could involve many aspects, e.g., power consumption, GPU and graphics memory costs, cloud service charges and token-level API expenses, etc. In this paper, we instantiate this metric for Coke in two ways; one can define the cost other ways under our framework. (i) fels (S). This intuitively indicates the cost of money particularly for comparing with series of LLMs from OpenAI, e.g., GPT3.5 and GPT4, (ii) Calls (times). We generalize the evaluation to open-source LLMs like Llama and ChatGLM. It indicates the number of times that we invoke the LLMs. Since KGMs are considered far more cheaper for local and cloud implementation, the metric of calls is also expected to be as few as possible.
Cost Saving:
3 Approach: Coke
To achieve an effective model selection, we mainly aim to answer two research questions: (i) How can we balance the exploration and exploitation to find the best model for both accuracy and cost saving? Real-world questions are difficult to manually identify to apply LLMs or KGMs. We usually value the prior knowledge to select the most accurate and inexpensive model at present greedily, i... exploitation. However, we also wish to obtain sufficient posterior experiences from under-explored models so far, i.e., exploration to find more models with superior performance-tor -or--ticee-eeee--e ratio. (ii) How can we automatically distinguish the most promising expert models for different questions? The particular types of required knowledge vary among questions. This suggests careful selection to leverage the specialized expertise from different models to make correct inferences. To this end, we design novel cost-efficient framework, Coke, to automatically select question-specif models.
We formulate the automatic model selection as a multi-armed bandit (MAB) problem. Specifically. in model m E M out of N candidate models, referred to as N arms. Let +h E {0, 1} denote the reward obtained by selecting E M. For each given question g. if the chosen model m
each iteration & < K, our policy is presented with the choice of selecting
the model m at the iteration k, where can correctly answer it, the policy will receive a positive reward of 1, and O vice versa. We aim to maximize the cumulative rewards in IC iterations and formulate the objective follows:
K
max
m
In each iteration, the selection is inherently associated with expectation function B(-) to capture the implicit linear correlation between the given question q and the potential reward r, indicating the likelihood of success by choosing one particular model m.
3

---

3.1 Accuracy-Cost Trade-off for KBQA with LLMs
To answer the two aforementioned questions, we decompose the expectation E(r (g) into three aspects. First, we calculate the accuracy expectation of one cluster, i.e., LLMs or KGMs, for better inferential performance(*).. Second, we design context-aware expert distinguishing to present the question embedding to the policy and find the best arm with implicit expertise (**), which further increases the probability of achieving higher accuracy for different question contexts. Finally, we constrain the decision-making with a cost regret. This is introduced to punish the model which wastes more on failures (***). The overall expectation is correspondingly formulated as follows.
E(rr (gx) (re (r 14)) -X R. (B,p(a))))
where r'm E {0, 1]. re and ra are the decomposed rewards for cluster sampling in terms of accuracy and arm selection considering knowledge expertise for particular questions. B indicates the limited budget allocated to invoke LLMs. Details are described hereunder.
3.2 Accuracy-Encouraged Cluster Expectation (*)
To encourage the policy to select more promising models, we first establish higher-level expectation concerning the overall accuracy performance of KGMs and LLMs. Inspired by the traditional Thompson Sampling, which iteratively samples the best arm based on historical information, i.e., success and failure, we thereby design a tailored cluster-level Thompson Sampling to evaluate the expectation of choosing one particular cluster c. It presents a dynamic approach where the selections evolve over iterations based on success and failures, gradually converging towards optimal selections as more questions are encountered. This could also effectively embody the exploraiion-exploitttoon trade-off inherent in our model selection scenarios for the sake of accuracy.
Specifically, it is established based on the prior knowledge as (success, failure) of each cluster, instantiated by a Beta distribution of Beta(a, 3). We define this pair of conjugate prior below.
conjugate prior of a and 3. Given a cluster c E {CL, CK ). let ae and Be denote the success and failure prior respectively for The pair of (ac, (Gc) forms conjugate prior. It faciliaates the efficient update of fundamental beliefs about the performance of each cluster c during selections.
Definition:
In general, we consider our cluster-level accuracy expectation E, as likelihood of success for each cluster by randomly sampling an indicator 0f: in iteration à from the distribution of (ela ,3 3k-1) based on the observation of success and failure in the former (k- 1) rounds.
(r (e)) & 0g ~ -
where 9g is distributed approximately uniformly across the entire interval, resulting in a uniform exploration when a particular cluster has not been extensively sampled. Otherwise, if cluster c has been sufficiently selected and the performance turns out to be satisfying with more success times, i.e., larger a.. the corresponding expectation associated with 0r will be more likely to be higher to facilitate reliable exploitation. When & O, we value the prior knowledge of cluster expectation before any observations have been made. In our paper, we utilize the average reported performance of each arm within the cluster as the prior for 0g. This ensures an empirically grounded initial belief' about the success probability of the cluster, as well as for subsequent Bayesian inference.
T(ah- -
prior
T(ac ) T( 0---1 (1 (1)
(4)
where r(-) is the Gamma function. Based on this, we consider the cluster with the largest 0 in iteration i as the best cluster e" for current question g, where the arm models within this particular cluster will have higher chances of answering this question. A reward re E {1, 0} will then be given e" can/cannot make the correct prediction. Correspondingly, the posterior distributions for all the historically selected clusters will be updated when 0 < k < K. The history of cluster sampling and the posterior updating formulated as follows, respectively.
H. [ci, a 1,8t-1 .
1, 2 1, 1,2...N
T(a -1 + gk- 11)
(0:) 4 (1- 1 (5)
posterior(0.) ~
I(a k-1 + r T + 1 1)-

---

While the exact sequence of cluster selections may vary between runs, the overall behavior will eventually converge to optimal cluster selections over time in our modeled MAB problem, especially as more questions are presented and more historical success/failure information is observed.
In iteration k, we denote the real-selected arm as ok, the annotated best arm as ag which can answer the question with the lowest costs. We refer to the expectation differences between og and dg as the selection regret for current iteration k.
Definition:
Selection Regret.
Specifically, we give the overall selection regret bounds for the cluster-level Thompson Sampling as follows. Given the selected arm ag and the historical information Hş up to iteration k, E, is bounded as follows: (The detailed proof of confidence bound is provided in the Appendix Section
SR(K) S +
+
Bir(on, Ha-1)]-
(6)
In general, the bounds are obtained from the following derivations. Initially, we establish the upper and lower confidence bounds as explicit functions of the arm aş and history H respectively, denoted as U(x H)-1) and Hx-)) For some > 0 and the number of arms N,, the specific form of functions U and L is irrelevant as long as they satisfy the following properties:
Va, k B[[U(a, Ha-1) - -[a)][(]]]] K.N
Va, k, B[[u(a)- - Lia Ha-1)] K-N
3.3 Context-Aware Expert Distinguishing (**)
To answer the second question, we further deepen our MAB problem as contextual variant. In this part, the expectation is highly related to the question semantics. We aim to automatically learn from the vector representation of questions, e.g., q R d for dimension, and effectively identify the corresponding expert model to answer it. The embedding is uniformly obtained by applying a lightweight pre-trained language model RoberTa (27). To this end, we design the expectation function E, (r314") to effectively capture the linear correlation between q and ra in iteration k.
E. (rālg") = qr x 1 +22+00 n/
(8)
where - E IR. 1xd is learned vectored parameter associated with each arm a in h steps. We introduce n as trainable noise Gaussian distribution (o, (²) ) to balance the exploration and exploitation. We maximize q² 1 to encourage the exploitation [TO. The tight correlations are established among the given question, the history information, i.e., Hk-1 including all the
questions Q E (xx-))xd answered by arm and the rewards received r E Ri in k-1 iterations. We could observe the history H. for each arm for abundant information for reference as:
H {a, Q .r. .r T = 1, 2. 1, n. 2...NN
Specifically, we update F based on the H with a typical ridge regression f(-)-
S(Q *- .ra
k-1 )- Σ (r k-1 Qk- -.,) + a |l μ 11
(10)
(1-- ( d ((ut) p. + ((()) = (rt-11 Q. (m
where we introduce the L2 normalization to ensure the reversibility of Q. in addition to the original ordinary least square loss. a solves the over-fitting problem by adopting suitable X. To find the optimal value of E that minimizes the cost function, we differentiate the formula with respect to p set the derivative equal to zero, and solve it. This yields the following update equation:
- =
Q + o. (Q
(11)
where I E Bdxd is an identity matrix. To facilitate exploration on less explored arms, we adopt an upper confidence bound for exploration-exploitaan with the probability least (1 8), the expectation Eg (r bounded by a confidence interval:
trade-off by introducing n/=1, For any 5 >
"qu q qupaa k-1 -y (7 E. s < ueat +7 fx(Q%
(12)
5

---

where y is a constant value, i.e., y =+ (m Also, we can derive the correlation term f7((a=))) as fr _ Va (1Q Q + =1) (qt) Hence, through learning from the current question qe E I2 and all historically assigned questions Q [[=-1)xd for arm a, can simply derive the equation appropriately update the noise term n// for next iteration.
qr ((Q Q oal) (q")T.
(13)
Maa
When arm with larger q" _ - is selected, this reflects an exploitation process. Similarly, when the model chooses an arm with larger n learned in previous iterations, this variance shows an exploration process since the model performs few selections of the current arm. Thus, jointly maximizing (q fha n/= helps us for more promising expert models subject to question q².
In conclusion, guided by the objective of maximizing cumulative rewards r we concentrate on the sub-target of finding contextually best arm the expert to correctly answer the question by prioritizing the arm with higher expectation E, (ral9") to obtain r..
3.4 Cost Regret Constraint (***)
Since the budget is limited, we aim to make the best use of the chances for both accuracy improvement and cost savings. this part, we introduce penalty term cost regret, denoted as Ra, to measure the proportion of costs incurred by incorrect predictions given by the arm within a budget constraint.
R. Evcof p(ax) |1
EgelQguel) p(ax) va
(14)
8.4.
Σ p(ax)llaal p(a))) s B: E A. )E(
where oh and Qh indicate the failure, i.e., the question and historically assigned questions for arm a that are wrongly answered. p(a) is the unit cost for invoking the LLMs. For black-box LLMs, calculate p(a)llqa as the token-level fees; while for open-sourced LLMs, it will be replaced by the times that call LLMs. The numerator of Ra represents the total cost incurred by incorrect answers given by arm a, while the denominator calculates the total cost of all questions answered by arm a. The constraint could effectively ensure that the total cost of selecting arm a for answering questions in the previous k- iterations and the current iteration & does not exceed a predefined budget B. To control the impacts of over-constraint from cost regret which may penalize the model for the costs on necessary trials, we introduce À as a hyperparameter to control the trade-off between maximizing rewards and minimizing cost regret for a reasonable exploration and exploitation.
4 Experiments
We conduct experiments on three domain-specine datasets: (i) Commonsense knowledge domain: CommonsenseQA [55;
(ii) Scientific Openbook domain: OpenbookQA 28]; (iii) Medical Domain:
MedQA-USMLE 223 To compare the performance of Coke, we include the baselines from three aspects, i.e., fine-tuned Language Models, KGMs and both API series and local series of LLMSs. Additionally, our framework is efficiently runnable one CPU. To accelerate the matrix computation, we adopt Torch to boost the selection on an NVIDIA GeForce RTX 4090 GPU.
4.1 Datasets
Commonsense (35 (abbreviated as CSQA) is prominent dataset in the commonsense knowledge domain that demands extensive real-world commonsense knowledge. encompasses 12, ques- tions, and ConceptNet 33), one of the largest commonsense knowledge graphs (KG), is frequently employed by existing KGMs for reasoning. Due to the official test set being reserved for leaderboard evaluations, we assess model performance using the in-house (IH) data split as implemented in (25). OpenBookQA (88 (referred to as OBQA) is a scientific domain dataset that comprises 5,957 multiple-choice questions from open book exams, each with four options. Answering OBQA ques- tions necessitates comprehensive understanding of fundamental science facts and their applications, which involves understanding scientific principles and applying them to novel situations.

---

Table 1: Performance comparison among kate-of-theean baselines and Coke three benchmark datasets terms of both inferential accuracy and cost saving ($ API fees).
CommonsenseQA
OpenBookQA
MedQA
Model
IHdev-Ace. IHlest-Acc. Dev-Acc. Test-Acc. Dev-Acc. Test-Ace.
Fine-dtuned Language Models (LMs)
Bert-base
0.573
0.535
0.588
0.566
0.359
0,344
Bert-large [
0,611
0.554
0,626
0,602
0.373
0.367
RoBerta-large
0.731
0.687
0.668
0.648
0.369
0.361
Knowledge Graph Based Small Models (KGMs)
MHGRN
16
0.745
0.713
0.786
0,806
QA-GNN
37
0.765
0.733
0.836
0.828
0.394
0.381
HamQA
14
0.769
0.739
0.858
0.846
0.396
0.385
JointLK
0.777
0.744
0.864
0.856
0.411
0.403
GreaseLM
39
0.785
0.742
0.857
0,848
0.400
0,385
GrapeQA
36
0.782
0.749
0.849
0.824
0,401
0.395
Large Language Models (LLMs)
Local Series
ChatGLM
0.473
0,469
0.352
0.360
0.346
0.366
Baichuan- 7B
0.491
0,476
0.411
0.395
0.334
0,319
Llama2 (7b)
0.561
0.547
0,526
0,466
0.302
0.299
Llama3 (8b)
0.754
0.720
0.762
0.756
0.622
0.691
Coke (Ours)
0.627
0.692
Acc. Imp.% vs. Llama3 (8h)
+ 0.81 %
+ 0.16% %
Cost Sav. (calls) % vs. Llama3 (8h)
-1.17% %
0.66 %
Large Language Models (LLMs)-
API Series
GPT3
0,539
0.520
0.420
0.482
0.312
0,289
GPT3.5
0.735
0.710
0.598
0.600
0.484
0.487
GPT-4
0.782
0.802
0.898
0.902
0.739
0.770
Coke (Ours)
0.802
0.824
0.902
0.908
0.746
0.778
Acc. Imp.% vs. GPT-4
+ 2.2666 %
2.74%
1.12%
0.67 %
+ 0.95%
+ 1.03%
Cost Sav. ($) % vs. GPT-4
11.114%
20.89 %
5.33 %
11.02% %
2.11% %
4..2%
MedQA-USMLE 23 i.e., MedQA, serves as domain-specific question-an question-answering -nwwering benchmark focused on medical knowledge. This dataset is derived from the United States Medical Licensing Examination, which is comprehensive and challenging assessment used to evaluate the competence of prospective medical professionals. MedQA includes variety of question types that test clinical knowledge, diagnostic reasoning, and medical science applications. The dataset benchmarks the performance understanding and applying medical knowledge both healthcare and medicine.
4.2 Baselines
Fine-tuned Language Models abbreviated as LMs. We evaluate our method against standard fine-
tuned language models, specifically using Bert-base, Bert-large (11), and RoBerta-large [27].
KGMs We include off-the-shelf small KGMs that integrate KGs for KBQA, including MHGRN [16]
QA-GNN (37], HamQA (14), JointLK 34, GreaseLM [39], and GrapeQA [36].
LLMs Our comparison includes two categories of LLMs: the API series (GPT-3, GPT-3.5, and
GPT-4) and local series (ChatGLM, Baichuan-7B. Llama2 (7b), and Llama3 (8b).
4.3
Main Results
The overall performance is compared and shown in Table To compare with API series of LLMs, we assemble HamQA, GPT3.5 and GPT-4 as the arms and our proposed Coke has outperformed all four categories of baselines in terms of inferential accuracy. Specifically, we could achieve 2.03%. 0.67% and 1.03% improvements over GPT-4 three datasets. For the local series of LLMs,

---

adopt HamQA, Llama2 (7b) and Llama3 (8b). Since Llama2 (7b) and Llama3 (8b) underperform the traditional KGMs with lagging performance on both CSQA and OBQA, we merely conduct the experiments on MedQA with the arm models, i.e., HamQA, Llama2 (7B) and Llama3 (8B). We conclude our observations hereunder. The performance gap among different arms plays vital role in balancing the accuracy and costs. For example, on CSQA and OBQA, the accuracy of state-of-the-art KGMs are very close to GPT-4 and much better that both GPT 3.5 and local series of LLMs. This facilitates a big improvements accuracy with much lower costs, i.e., 20.89% and 11.02%. However, on MedQA, where the questions over-complicated and open-ended for KGMs to infer, there exists huge performance gap between the best KGM and all the LLMs, especially when compared with GPT-4. Our policy has to rely on sufficient calls of LLMs to ensure accuracy, which indeed increases the costs.
cost saving by invoking more KGMs, where we achieve higher
4.4 Hyperparameter Analysis
In this subsection, we conduct a detailed analysis of the important hyperparameters, i.e., and B.
4.4.1 Budget Study
Toke-CSQA
The Pareto frontier for both inferential accuracy and cost sav- ing is shown in Figure 2 For clear illustration, we replace the accuracy with the error rate which reversely shows the direction of performance changes. To observe when the ac- curacy and cost reach the balance, we decrease the budget from 1 to 0.5 until Coke has higher error rate than GPT-4 (00.500.6,0.7.... J. In this figure, nodes in the lower left positions imply better performance considering both higher ac- curacy and lower costs. Specifically, our proposed Coke could achieve comparable performance GPT- within around 60% budget on both CSQA and OBQA datasets. On MedQA, the slope rapidly drops before the budget ratio reaches 95% and finally outperforms GPT-4 after B 2 0.95. Since budget B strictly constrains the opportunities to call L.Ms,, intuitively, more budgets for L.MSs will lead to higher accuracy most scenarios. However, this does not practically stand for KBQA since the domain knowledge in LLMs is limited. Moreover, purely relying on LLMs will also lose the opportunities leverage KGMs further boost the accuracy. On the other hand, more budget will inevitably increase the token-level costs. Consequently, our proposed Coke has outperformed GPT-4 on all the datasets with higher accuracy as B increases. It effectively moves the Pareto frontier for KBQA with LLMs.
Loke-OB0A
Coke-NedOA
0.3
OBGA
0.2
0.5
Budget
Figure 2: A visualization of Pareto frontier of both inferential accuracy budget B in-
and cost saving creases on three datasets.
4.5 Observations on search of À
The hyperparameter À is essential for controlling the constraint from cost regret within our framework. We face a dilemma to cautiously decide the value of X. On one hand, we aim to adopt a large value to strictly penalize models that allocate more resources to failed attempts. On the other hand, over-penalty will damage the exploration during selection, which means the penalized models will no longer be invoked. Thus, carefully adjust À within (0.001, 0.1, 1, 10, 100} to modulate the extent which we minimize cost regret versus maximizing accuracy. The visualization of performance, i.e., inferential accuracy and cost saving, is shown in Figure 3 Consequently, we conclude our observations as follows. A higher À value signifies a stronger emphasis on cost- efficient decision-making making. potentially leading to more conservative model selections. Conversely, lower À value may prioritize accuracy over cost savings, resulting in a higher tolerance for resource expenditure on exploration. We adopt the wave peak value of 1 for the final reported performance.
Search of A
0SO4
0R04
0.85
MedOA
0.80
0.75
10
Figure 3:
Performance changes based on the search of X.
4.6 Ablation Studies
In this part, we investigate the importance of each decomposed expectation in our overall objective of optimization, i.c., E. and Eg, as well as the constraint from cost regret R.. The performance of
8

---

Table 2: Verification of the importance of R. B,g and R. on three datasets.
CommonsenseQAA
OpenBookQA
MedQA
Ablations
Accuracy
Cost Saving (S)
Accuracy
Cost Saving ($)
Accuracy
Cost Saving (S)
w/o E.c
0.750
447.59%
0.855
-32.10%
0.607
300.51 %
w/o IE..
0.801
-15,42%
0.880
-21.16%
0.760
- -1.07% %
w/o Ra
0.800
-6.26% %
0.898
-3.31 %
0.684
15.98 %
Coke
0.824
-00.89%
0.908
-11.02%
0.778
-4.32%
inferential accuracy and cost saving by removing one component are shown in Table Removing E, leads to significant reductions in cost savings across all datasets. Specifically, cost savings decrease by 47.59% for CSQA, 32.10% 10% for OBQA, and 30.51 for MedQA. While The exclusion of E. results in noticeable reductions in accuracy, especially for MedQA, where accuracy falls to 0.760. Finally, removing R. brings decreases both accuracy and cost savings across all datasets. The observations suggest the unique contribution of each component to the model's overall performance.
-30
Pagget
Selecton Regrec
100
-100
25
110
110
-175
-30
10 1.5 25
Ams
2000000000p00000000 Berations
1.0
2.0
2.5 Amss
200
300
10
2.0
3.0
Figure 4: A 3D toy visualization of the selection regret on three datasets as iteration & goes.
4.7 Selection Regret Analysis
Additionally the proof of the expectation bounds of both E. and Ey we comprehensively evaluate our model selection by visualizing the selection regret in 3D figure across three datasets in Figure 4 For a clear demonstration of the performance changes, we instantiate the expectation gap ( [xa=)] between best arm az and the selected arm with a toy example as {-1,0) which indicate the regret of choosing aj. sheds light on an intuitive understanding of how regret evolves and converges quickly over iterations, offering valuable insights into the model performance and the correctness of our selection strategy. highlighting the strengths of our proposed method.
4.8
Case Studies
To provide insights into the effectiveness of Coke balancing inferential accuracy and cost saving, we visualize the distribution of model selection on CSQA, OBQA and MedQA in Figure respec- tively. We could clearly observe the exploration process when the color of cubes in the heatmap changes from deep to shallow, e.g., (250, 500) intervals on CSQA and MedQA for GPT-4. This makes trials and spends necessary costs on the under-explored model. While the color changes from shallow to deep, c.g., [250, 500 intervals on CSQA for HamQA, (500, 750) intervals on CSQA and MedQA, [100, 200 on OBQA for GPT-4 and (750, 1000) intervals for ChatGPT, indicating the exploitation process that leverages the best model. The case study sheds light on our superior ability balance the selection for more accurate and cost-saving candidate models.
5 Related Work
Contemporary research has been focused on generating answers through deductive processes applied knowledge graphs, as outlined in surveys and studies on the subject [24 22]. Existing methods predominantly leverage techniques rooted in semantic parsing and information retrieval [i (6).. For instance, KagNet 25 introduces a schema graph that adeptly captures relational paths among pivotal entities. Nonetheless, these methodologies often delineate the processes of question interpretation and knowledge graph (KG) inference as distinct stages, thereby exposing the models to potential pitfalls associated with the nuanced or implicit facets of query phrasing, including negations and

---

HamQA
ChatGPT
GPT-4
HamQA
ChaRGPT
GPT-4
HamQA
ChatGPT
GPT4
200
0-250
61
145
D-100
43
80
0-250
25
177
250-500
122
21
107
Seeteons
100:200
11
80
60
250-500
11
124
115
500-750
35
201
100
200-300
90
500-750
223
100
59
95
4000-40--
75
750-1000
247
-50
-50
000-1221
55
79
87
400-500
7
13
8D
1000-1272
3
40
229
Figure 5: A case study of the model selection on three domain-specific datasets & goes. The color changes from deep to shallow indicates an exploration process, while an exploitation reversely.
contextual constraints. Recognizing this limitation, recent innovations have pivoted towards more integrated approach to reasoning. MHGRN [66] exemplifies this trend by dynamically refining the embeddings of the question context in tandem with the reasoning process, utilizing graph neural networks. This fusion of path encoders with GNNs not only enhances the model's interpretabiliiyy but also its ability to scale. Building on this, the QA-GNN framework [37] goes further by crafting work graph wherein the context itself is instantiated as entity and interlinked with relevant entities through cooccurrence, thereby streamlining the reasoning process. GreaseLM [3]] establishes tighter connection between language models and KGs with joint training mechanism. While HamQA [14] focuses on combining question understanding and knowledge reasoning, it excels in answering hierarchical questions containing hyponymys.
Limitation
Our study faces major limitation of the distinct performance gaps among existing models consid- ering both inferential accuracy and cost savings, c.g., KGMs and LLMs. This disparity from the underperformance of certain models hinders the overall efficiency of model selection. For example, on MedQA dataset, the gap between the best KGM and GPT-4 is remarkable 36.50% This forces policy rely GPT-4 maintain accuracy, bringing higher costs. However, fast-pluggable policy, Coke can easily address this concern when more robust models appear to boost the selection.
7 Conclusion
In this paper, we present Coke, a novel cost-efficient strategy for LLMs in KBQA while balancing inferential accuracy and cost saving. Our work first formally defines the problem of trading off accuracy and cost for KBQA with LLMs and provides a practical solution for utilizing LLMs in essouce-consstrained and domain knwweedee-require scenarios. could effectively integrate two sets of off-the-shelf models, i.e., I.LMs and KGMs, and efficiently assign the most promising model for each question within limited budget by employing tailored cluster-based Thompson Sampling and a contextual multi-armed bandit. The former models the preliminary selection between LLMs and KGMs based on historical performance, while the latter identifies the best model within cluster according to question semantics. The overall decision-making is bounded by the cost regret, constraining the selection based on cumulative expenses incurred from model failures. Extensive experiments on three Nomain-speciff benchmark datasets demonstrate the superiority of Coke in terms of both inferential accuracy and cost-effectivesess. Our proposed framework could also offer significantly promising direction for efficient integration of LLMs in various knowledge based tasks.
Acknowledgement
The work described this paper was fully supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. PolyU 25208322).
10

---

References
[1] Ilaria Amaro, Attilio Della Greca, Rita Francese, Genoveffa Tortora, and Cesare Tucci. Ai unreliable answers: A case study chatgpt. In ICHCI, pages 23-40 40. Springer, 2023.
[2] Md Adnan Arefeen, Biplob Debnath, and Srimat Chakradhar. Leancontext: Cost-efficient domain-specific question answering using 1lms, Natural Language Processing Journal, page 100065, 2024.
[3] Yejin Bang. Samuel Cahyawijaya, Nayeon Lee, Wenliang Dai, Dan Su, Bryan Wilie, Holy Love- nia, Ziwei Ji, Tiezheng Yu, Willy Chung, et al. A multitask, multilingual, multimodal evaluation of chatgpt reasoning, hallucination, and interactivity. arXiv preprint arXiv:2302.0400 2023.
[4] Hao Chen, Yuanchen Bei, Qijie Shen, Yue Xu, Sheng Zhou, Wenbing Huang, Feiran Huang, Senzhang Wang, and Xiao Huang. Macro graph neural networks for online billion-scale recommender systems. In Proceedings of the ACM on Web Conference 2024, pages 3598-3608, 2024.
[5] Hao Chen, Yue Xu, Feiran Huang, Zengde Deng, Wenbing Huang, Senzhang Wang, Peng He, and Zhoujun Li. Label-aware graph convolutional networks. In Proceedings the 29th ACM International Conference on Information & Knowledge Management, page 1977-1980, 2020.
[6] Lingjiao Chen, Matei Zaharia, and James Zou. Frugalgpt: How to use large language models while reducing cost and improving performance. arXiv preprint arXiv:2305.055
2023.
[7] Shengyuan Chen, Yunfeng Cai, Huang Fang, Xiao Huang, and Mingming Sun. Differentiable neuro-symbolic reasoning on large-scale knowledge graphs. Advances in Neural Information Processing Systems, 36, 2024.
[8] Shengyuan Chen, Qinggang Zhang, Junnan Dong, Wen Hua, Jiannong Cao, and Xiao Huang. Neuro-symbolic entity alignment via variational inference. arXiv preprint arXiv:2410.04153, 2024.
[9] Shengyuan Chen, Qinggang Zhang, Junnan Dong, Wen Hua, Qing Li, and Xiao Huang. Entity alignment with noisy annotations from large language models. arXiv preprint arXiv:2405.16800 2024.
[10] Yifang Chen, Chung-War Wei Lec, Haipeng Luo, and Chen Yu Wei. A new algorithm for non- stationary contextual bandits: Efficient, optimal and parameter-free. In COLT. PMLR, 2019.
[11] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: meto:./00000000 2018.
[12] Junnan Dong, Zijin Hong. Yuanchen Bei, Feiran Huang. Xinrun Wang, and Xiao Huang. Clr-bench: Evaluating large language models in college-level reasoning, 2024.
[13] Junnan Dong, Wentao Li, Yaowei Wang, Qing Li, George Baciu, Jiannong Cao, Xiao Huang, Richard Chen Li, and Peter HF Ng. Gradual study advising with course knowledge graphs. In International Conference on Web-Based Learning, pages 125-138. Springer, 2023.
[14] Junnan Dong, Qinggang Zhang, Xiao Huang, Keyu Duan, Qiaoyu Tan, and Zhimeng Jiang. Hierarchy-aware multi-hop question answering over knowledge graphs. In Proceedings of the ACM Web Conference 2023, pages 2519-2527, 2023.
[15] Junnan Dong, Qinggang Zhang, Huachi Zhou, Daochen Zha, Pai Zheng, and Xiao Huang. Modality-aware integration with large language models for knowledge-basse -ased visual question answering, 2024.
[16] Yanlin Feng, Xinyue Chen, Bill Yuchen Lin, Peifeng Wang, Jun Yan, and Xiang Ren. Scalable multi-hop relational reasoning for knowledge-aware question answering. In EMNLP, pages 1295-1309, 2020.

---

[17] Jocelyn Gravel, Madeleine D' Amours--Grved and Esli Osmanlliu. Learning to fake it: limited responses and fabricated references provided by chatgpt for medical questions. Mayo Clinic Proceedings: Digital Health, 133):226-234 2023.
[18) Zijin Hong, Zheng Yuan, Hao Chen, Qinggang Zhang, Feiran Huang, and Xiao Huang. Knowledge-to-sql- Enhancing sql generation with data expert Imm, 2024.
[19] Zijin Hong, Zheng Yuan, Qinggang Zhang, Hao Chen, Jumnan Dong, Feiran Huang, and Xiao Huang. Next-gent setereeeerttion database interfaces: A survey of Ilm-based text-to-sql. arXiv preprint arXiv:2406.000 08426, 2024.
[20] Feiran Huang, Zefan Wang, Xiao Huang, Yufeng Qian, Zhetao Li, and Hao Chen. Aligning distillation for cold-start item recommendation. In Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, page 1147-1157, 2023.
[21] Feiran Huang, Zhenghang Yang, Junyi Jiang, Yuanchen Bei, Yijie Zhang, and Hao Chen. Large language model interaction simulator for cold-start item recommendation. arXiv preprint arXiv:2402.00 091 176, 2024.
[22] Xiao Huang, Jingyuan Zhang, Dingcheng Li, and Ping Li, Knowledge graph embedding based question answering. In WSDM, pages (13-113,22) 2019.
[23] Di Jin, Eileen Pan, Nassim Oufattole, Wei-Hung Weng, Hanyi Fang, and Peter Szolovits. What disease does this patient have? large-scale open domain question answering dataset from medical exams. Applied Sciences, 11(14), 2021.
[24] Yunshi Lan, Gaole He, Jinhao Jiang, Jing Jiang, Wayne Xin Zhao, and Ji-Rong Wen. A survey on complex knowledge base question answering: Methods, challenges and solutions. In IJCAI, 2021.
[25] Bill Yuchen Lin, Xinyue Chen, Jamin Chen, and Xiang Ren. Kagnet: Knowledge-aware graph networks for commonsense reasoning. In EMNLP-IJCNLP. pages 2829-28222222 2839,,839,2288 2019.
[26] Lihui Liu, Boxin Du, Jiejun Xu, Yinglong Xia, and Hanghang Tong. Joint knowledge graph completion and question answering. In KDD, pages 1098-1 108, 2022.
[27] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: robustly optimized bert pretraining approach. arXiv preprint arXiv: 1907. 2019.
[28] Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal. Can a suit of armor conduct electricity? a new dataset for open book question answering. In EMNLP, pages 2381-2391, 2018.
[29] OpenAl. Gpt-4 technical report, 2023.
[30] Diogo Teles Sant' Anna, Rodrigo Oliveira Caus, Lucas dos Santos Ramos, Victor Hochgreb, and Julio Cesar dos Reis. Generating knowledge graphs from unstructured texts: Experiences in the e-commerce field for question answering. In ASLD@ ISWC, pages 56-71, 2020.
[31] Apoorv Saxena, Aditay Tripathi, and Partha Talukdar. Improving multi-hop question answering over knowledge graphs using knowledge base embeddings. In ACL. pages 4498 4507,, 2020.
[32] Xinyue Shen, Zeyuan Chen, Michael Backes, and Yang Zhang. In chatgpt we trust? measuring and characterizing the reliability of chatgpt. arXiv preprint arXiv:2304.0891 08979, 2023.
[33] Robyn Speer, Joshua Chin, and Catherine Havasi. Conceptnet 5.5; An open multilingual graph of general knowledge. 2016.
[34] Yueqing Sun, Qi Shi, Le Qi, and Yu Zhang. Jointlk: Joint reasoning with language models and knowledge graphs for commonsense question answering. arXiv preprint 2 2021.
12

---

[35] Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. Commonsensequ: A question answering challenge targeting commonsense knowledge. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume (Long and Short Papers), pages 4149 4158, 2019.
[36] Dhaval Taunk, Lakshya Khanna, Siri Venkata Pavan Kumar Kandru, Vasudeva Varma, Charu Sharma, and Makarand Tapaswi. Grapeqa: graph augmentation and pruning enhance question- answering. In Companion Proceedings of the ACM Web Conference 2023, pages 1138-1144, 2023.
[37] Michihiro Yasunaga, Hongyu Ren, Antoine Bosselut, Percy Liang, and Jure Leskovec. Qa-gnn: Reasoning with language models and knowledge graphs for question answering. NAACL, 2021.
[38] Qinggang Zhang, Junnan Dong, Hao Chen, Daochen Zha, Zailiang Yu, and Xiao Huang. Knowgpt: Knowledge injection for large language models, 2024.
[39] Xikun Zhang, Antoine Bosselut, Michihiro Yasunaga, Hongyu Ren, Percy Liang, Christopher Manning, and Jure Leskovec. Greaselm: Graph reasoning enhanced language models for question answering. arXiv preprint arXiv:2201.08860 2022.
13

---

A Proof of Selection Regret in Cluster-level Thompson Sampling
The expectation bounds of the specific iteration is:
( = [[[({)]
(15)
[l(((a)) m(ax))]
(16)
HR- [B(u(aï] - p(ax))
Hx-ill R((((a)) U( Hx-1))
Note that ag ~ oj when Hx-1 is fixed
(17)
(aK, HK-1) p((ax))
(18)
Part
Part
According to the properties shown in Eq. 7 the part 2 can be deducted: Biu(ait) (ag. Ha Ha-1) )) & E((u(at) - U(k, Hx- 1])
<
E
Σ (m(as) - U(0,, Hn-1))
ak
E
Σ (m(as) - U(x, Ha-1))
(19)
(au Hu-1) - [
7
k
K k
Similarly, Eq. 7 suggests that the part is bounded as follows:
(ax Hx-1) - p(a=)] E|2r(ax, Ha-1) L(ar, He-1) p(an)]
= -Eirra(un Hu + Laa,,, Hx-1) - u(an))
E[L Ha-1) p(ax)] s E[(L(ax, Ha-1) - m(ax))+1
$ E
Σ (Llan, Hx-1) - x(ax))+
E ((ulan) (ax, H))+
(20)
E [u(ax) Leax, [
S K. k
k
? K
Putting part and Part together, SR, 2 + 2 + R/2r(a,, Ha-1)). Summing up over t, can be proved that SR(K) < 2x + 2 D == (/r Hx-1)).
B Broader Impacts
In terms of the potential positive impacts, our work may have impacts on the improved efficiency and better decision-makinn processes based on LLMs with lower costs in many Nomain-speciffi tasks. The potential benefitted scenarios and group of people can be education, medical and healthcare for both research and application. We may also be able to reduce commercial costs for enterprises and innovations in the industry.
This paper does not present any foreseeable negative impacts to society since we focus on the technique of optimizing model selection policy that is purely serving the KBQA task.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The major contributions the community have been clearly highlighted in both the Abstract and Introduction. In this paper, we focus on knowledge- basedd question answering with LLMs. Our moving the Pareto frontier and contributions will definitely inspire the community followed by more meaningful work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In Section we clearly demonstrate one potential limit of our work brought by the performance gap among existing models. However, as a fast-plugged framework, the limitation can be easily avoided when more robust models appear. We can thereby boost the performance with our superior model selection policy.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specifiiattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
15

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: In Appendix Section A detailedly provide the derivative process of both the upper and lower confidence bounds for expectation E,-
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: To contribute and inspire more valuable research in the community, we have open sourcee our main codes for reproducibility. The codes could be found from this anonymous link: wtw.:/ooooooooooooococcceeee///e 2--------------A--- Gooke-Anoyymous 13626/main.py
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
16

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: To contribute and inspire more valuable research in the community, have open-sourced our main codes for reproducibility. The codes could be found from this anonymous link:
2-c-------------AAoooo-- Coke-Anonymous-
13626/main.py
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
iulPoolccyy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7/nips.
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have detailedly introduced our adopted datasets in Section We also visualize the hyperparameter analysis in Section 4.4
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
17

---

Justification: In our paper, abundant of ablations have been done on all three benchmark Nomain-speciff datasets showcase the superior performance of our proposed methods. We also provide an optimal seed to control the randomness during the sampling based on Beta distribution.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
We have demonstrated our used resources for the main results in Section ??. In- deed, our framework is highly usable with CPU only for general cases as well as commercial scenarios.
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We confirm that we have fully complied with the Ethics Policy in this study. We conduct experiments with widely adopted publicly available datasets. The codes are open-sourced for other researchers' further study in the active KBQA community.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
18

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: We have demonstrated potential positive impacts in Appendix Section B Also this paper does not present any foresceable negative impacts since we focus on the technique of optimizing model selection policy that purely serving the KBQA task.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairesss considerations (e.g., depllymeen of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification: We merely adopt pre-trained close-source LLMs on the benchmark knowledge-based QA datasets. The returned answers will only be choices based on careful in-context prompt design. There will be no harmful of risky content generated.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
19

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We conduct experiments on widely adopted benchmarks datasets that are publicly available. They are properly cited as the references in our manuscript.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We strictly follow the main stream of the KBQA community and leverage the existing datasets, as well as their splits with no new datasets used or curated.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not involve any human resources to manually annotate or evaluate.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
20

---

15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: We do not involve any human-related experiments our research. This paper only focuses the machine comprehension and model selection for knowledge-based question answering.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
21


Reviews:
[{"review_id": "Nd9SKXgawx", "reviewer": "Reviewer_HDrN", "summary": "The authors proposed a strategy to switch between LLMs and KGMs when performing Question Answering, aiming to optimize both cost and accuracy. The evaluation is performed on three datasets: CommonsenseQA, OpenBookQA, and MedQA.", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The authors address an important and practical problem, which is cost-saving in QnA. The introduction is well-written, and the intuition is nicely presented. The proposed idea to switch between KG-based models and LLMs depending on different questions makes sense and shows some promising results on the test datasets.", "weaknesses": "It lacks implementation details such as how the model is trained, which models are being used as LLMs and KGMs, and the exact formula/implementation of the cost functions.\n\nThe proposed solution is based on cluster-level Thompson Sampling, but it lacks an explanation of why it's the best candidate for this setting. Additionally, defining the cost function as the number of calls is less practical; instead, it should be a function of latency and API fees (assuming the use of GPT-4).\n\nThe result of cost-saving is promising but not as high as expected. From Figure 1c, it seems that about half of the questions can be answered by KGMs. However, the experimental cost-saving shown in Table 1 is only 10%-20%. This suggests there is still room for improvement in the decision-making model.\n\nThere is almost no benefit when using it on MedQA, so one weakness of the solution is that it heavily depends on the performance of the KGMs to save costs", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your recognition of our contributions to a very important and practical problem. We value your insightful comments and will carefully revise the final version following your suggestions. \n\n> Response to weaknesses\n* **W1: Implementation details**.\nThanks for raising these points. In the original main result, we use HamQA, GPT 3.5 and GPT-4 as KGMs and LLMs.\n- *Framework training*. We provided two pseudo-codes in the PDF of general response to demonstrate the process. The optimization is under a Bayesian online learning framework where our model keeps learning with new queries before using up the budget and continuously updates the parameters based on historical observations. This enables us to be generalizable to any unknown scenarios. \n- *KGM pretraining*. We pretrain the base KGMs based on the training dataset. We carefully checked and ensured the data distributions among train, dev and test are identical. The pre-trained KGMs are directly leveraged for inference without further training.\n- *Cost functions*. We do not necessarily utilize a cost function since our model is optimized under Bayesian online learning. More generalizably, after defining the parameter prior, we calculated the posterior probability according to the feedback from LLMs. Instead of minimizing the cost function, we aim to optimize the expectation function and update the parameters including: 1. posterior distribution Beta($\\alpha^{k−1}_{c}$, $\\beta^{k−1}_{c}$) for clustered-Thompson Sampling 2. $\\mu^{k−1}_{a}$ and $\\eta^{k−1}_{a}$ for contextual MAB.\n* **W2-1: Mechanism of Thompson Sampling**.\nThank you for the comment. We have added two pseudo-codes in the PDF of the general response to demonstrate: 1. clustered Thompson Sampling 2. contextual MAB.\n\n* **W2-2: Evaluation metrics**.\nThanks for your constructive comments, we are inspired to have two more metrics **`Inference Latency`** and **`Cost Advantage`**. We also quantified the costs of KGMs and local LLMs with **`cloud service fee`** to address your concerns. In our submission, we have already included two metrics '**calls**' and '**API fees**', where calls are used for open-source LLMs and API fees are for GPT series. This also showcases that our evaluation can be general and easily adapted to various metrics. We show the new results on three benchmark datasets as follows.\n**`Inference Latency (s)`**: the time span between question input and prediction output in seconds.\n**`Cost Advantage (%)`**: used in HybridLLM-ICLR'24, as the percentage of questions answered by small models.\n**`cloud service fee`**: calculates the token-level cost based on basic requirements of GPU resources in cloud servers, instantiated by AWS g4dn.xlarge and p3.8xlarge with USD 0.526 and USD12.24 per hour.\n\n|                    |  Inference Latency (s)  | Cloud/API Fees ($) |  Inference Latency (s)  | Cloud/API Fees ($) |   Inference Latency (s)  | Cloud/API Fees ($) |\n|:------------------:|:-----------------------:|:------------------:|:-----------------------:|:------------------:|:------------------------:|:------------------:|\n|        HamQA       |          340.60         |        0.005       |          425.60         |        0.004       |          671.25          |        0.009       |\n|      GreaseLM      |          462.17         |        0.007       |          503.44         |        0.005       |          762.17          |        0.013       |\n|      Llama2 7B     |          61.20          |        0.20        |          60.00          |        0.20        |           61.20          |         0.4        |\n|      Llama3 8B     |          50.01          |        0.20        |          47.58          |        0.20        |           50.01          |         0.4        |\n|       GPT 3.5      |          26.33          |        0.05        |          27.29          |        0.02        |           26.33          |        0.15        |\n|        GPT-4       |          20.67          |        1.01        |          18.16          |        0.38        |           20.67          |        3.03        |\n|  Coke-HamQA (Ours) |          70.59          |       -20.16       |          58.25          |       -10.85%      |           46.12          |       -4.05%       |\n| Coke-Llama3 (Ours) |          36.22          |       -17.52%      |          25.37          |        -8.2%       |           30.41          |     **-41.92%**    |\n| Coke-Llama3 (Ours) | **CSQA Accuracy Imp%:** |       +2.48       | **OBQA Accuracy Imp%:** |       +0.58       | **MedQA Accuracy Imp:** |       +3.26       |\n\n| Cost Advantage (%) |  CSQA  |  OBQA  |  MedQA |\n|:------------------:|:------:|:------:|:------:|\n|  Coke-HamQA | 20.89 | 11.02 |  4.32 |\n| Coke-Llama3 | 18.62 |  9.70 | 48.55 |\n\n* **W3: Performance Improvements**.\nThank you for initiating the discussion. First, cost savings between 10% and 20% is already satisfying industrial applications. For example, a typical intelligent customer service in large e-commercial company will handle around 3M tokens a day, after applying our framework, the cost saving can be remarkably around 6600 USD\\$ a year. Second, in the table for W2, we showcase the performance of using cheaper LLMs (Llama3 7b) with GPT3.5 and GPT-4. When we adopted Llama3 to replace KGMs on MedQA, the performance was boosted with over 41.92% savings and 3.26% ACC improvements.\n\n\n* **W4: Importance of KGMs**.\nWe are grateful and excited to claim that this limitation is no longer constraining our paper after being guided by all reviewers. First, this limitation can be easily solved since we are a fast-adaptive and pluggable framework. We can readily involve advanced KGMs given prosperous community to achieve higher performance. Second, this limitation can also be solved by using cheaper local LLMs than KGMs. Evaluated by cloud service fees, the results have been provided in the previous rebuttal, and we can achieve 41.92% cost savings while improving the accuracy around 3.26% on MedQA.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0sxuypLjfD", "reviewer": "Reviewer_FvaD", "summary": "This manuscript presents a novel cost-efficient strategy to leverage LLMs for knowledge-based question answering. It could balance both inferential accuracy and cost saving. Several SOTA methods, inlcuding both traditional KGQA methods and LLMs are combined since KGQA models are small and knowledgeable but less accurate, while LLMs are comprehensive on general questions but rather expensive. Authors design a cluster-based TS technique and a tailored contextual MAB to filter out the experts and constrain the decision with the consideration on cost regrets.", "questions": "1: It will be interesting if the author can apply existing methods in other domain as baselines and make a comparison. Have the authors try the methods in other domains like FrugalGPT and HybridLLM and migrated them into KGQA?\n\n2: The reviewer is interested to see more combinations of base models. Have you tried different combinations?", "limitations": "Yes.\n\nThe limitation is acknowledged by the authors, which is from the performance constraint by base models. It should be easy to address by replacing the base models with more advanced ones. While the selection of models requires much prior knowledge of performance, this may be a concern on additional resource consumption.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This propsed method has fhe following strengths:\n\n1. Saving costs of invoking LLMs while obtaining higher accuracy is a promising topic with both academic merits and industrial values. It could be somehow inspiring various research communities.\n\n2. The proposed methodology is novel and reasonable. It considers the model selection based on three aspects: the accuracy potential of choosing one model based on historical success, the expertise on particular questions based on the question semantics and the cost regret from the expenditure on historical failure to control the costs.\n\n3. Sufficient theoretical analysis and proofs, e.g., expectation bound of Thompson Sampling and the confidence bound for MAB to correspondingly support the design of automatic selection.\n\n4. Nicely drawn running example is easy for grasping the motivation. It provides a sketched overview of the pipelines, the performance/cost comparison of existing methods and the overlaps among different models. This motivates the combination of KGMs and LLMs with a auto-selection algorithm.\n\n5. Satisfying experimental performance on both accuracy and cost saving performance.\n\n6. The writing is good and clear to follow.", "weaknesses": "1. A pseudo-algorithm should be provided to demonstrate the selection process and how the Thompson sampling and MAB decides in each step.\n\n2. The results are currently from one fixed combination of base models, i.e., HamQA + ChatGPT+ GPT4. It will be more solid to provide the results of different combinations of base models as additional ablation studies. For example, I may like to see the results with GreaseLM + HamQA as the clustered arms for KGMs and ChatGPT+GPT as the ones for LLMs.\n\n3. Missing references for ChatGLM Baichuan and Llama2/3 in the main table.\n\n4. More heuristic baselines should be included, for instance, (1) $E_c$ + random $E_a$; (2) random $e_c$ + random $E_a$ (3) pure random selection without $E_c$, $E_a$ and $R_a$ (4) epsilon greedy-based selection with $E_a$ only.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to gratefully thank you for your strong support! We also cherish your expertise for plenty of professional suggestions. It is encouraging to be acknowledged by experts from the community. We believe your insightful comments will greatly help us to enrich the experiments and further demonstrate our contributions.\n\nFollowing your suggestions, all the newly demonstrated algorithms and experiments will be added to the final revised version.\n> Response to weaknesses\n- **W1: Algorithms and pseudo-codes**. \nThanks for your constructive suggestions. We have provided four pseudo-codes in the PDF of the general rebuttal, which demonstrates the training and inference stage of our main framework, as well as the cluster-based Thompson Sampling and contextual MAB. Please kindly check the details in the PDF.\n- **W2: Base model combinations**. \nWe appreciate your insightful comments on a meaningful ablation study. We have done some preliminary trials during our experiments. Some intuitive results are shown hereunder over CSQA dataset. We observe that, both the quality and the number lay an indispensible influence on the final decision. As a fast-adaptive framework, we can readily include more advanced and cheaper base models to move the Pareto frontier for KGQA considering both higher accuracy and lower costs.\n\n|                                | 3       | 3 | 4       | 4 | 5       |\n|-----------------------------|-----|-----|-----|-----|-----|\n| HamQA                      | Picked |  -   | Picked |   Picked  | Picked |\n| GreaseLM                  | -         |  Picked   | Picked |   -  | Picked |\n| Llama3 (7b)               | -         |   -  | -         |  Picked   | Picked |\n| GPT 3.5                     | Picked |   Picked  | Picked |  Picked   | Picked |\n| GPT-4                        | Picked |  Picked   | Picked |  Picked   | Picked |\n| Coke (Ours)               | 2.74%  |   2.66%  |     1.89%     |   1.05%  |     0.41%     |\n| Cost Sav. (Cloud/API fees) | 20.16% |   21.50%  |    20.92%      |  19.84%   |     36.01%     |\n\n\n- **W3: Missing references**. \nThanks for your carefulness, we have properly added citations for both LLMs.\n- **W4: Heuristic Baselines**. \nThanks for your guidance, we have implemented the heuristic methods on all three domain-specific datasets. For epsilon-greedy, we have set the threshold as '0.7'.\n\n|          (Acc. Imp%)          |   CSQA  |   OBQA  | MedQA   |\n|:-----------------------------:|:-------:|:-------:|---------|\n|        E_c + Random E_a       | 2.21%   | 4.69%   | -0.4%   |\n| Cost Sav. (Cloud/API fees)    | 1.50%   | 0.38%   | 0.03%   |\n|   Random E_c and Random E_a   | -10.32% | -3.19%  | -15.88% |\n| Cost Sav. (Cloud/API fees)    | 1.50%   | 2.05%   | 12.41%  |\n|     pure random selection     | -62.51% | -45.27% | -84.40% |\n| Cost Sav. (Cloud/API fees)    | 64.48%  | 53.98%  | 70.25%  |\n| epsilon greedy-based MAB only | -12.79% | -22.54% | -12.79% |\n| Cost Sav. (Cloud/API fees)    | 9.76%   | 17.61%  | 8.06%   |\n|       Coke-HamQA (Ours)       |  2.74%  |  0.67%  | 1.03%   |\n| Cost Sav. (Cloud/API fees)    |  20.16% |  10.85% | 4.05%   |\n> Response to questions\n- **Q1: Migration Study from other domains**.\nThank you for providing these two references. We will properly cite them in the related work section. For FrugalGPT, we set the threshold for switching KGMs to LLMs as '0.85' after necessary hyperparameter tuning.\n\n|           |  CSQA  |   OBQA  |  MedQA  |\n|:---------:|:------:|:-------:|:-------:|\n| HybridLLM | 1.26%  | -3.55%  | -19.98% |\n| FrugalGPT | -2.51% | -10.79% | -32.51% |\n\n- **Q2: Base model combinations**.\nThanks for your valuable question. Yes, we have provided our observations and preliminary results in the aforementioned rebuttal.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "G7eKUI4Agm", "reviewer": "Reviewer_JWNj", "summary": "The paper introduces a method for deciding whether to use a Large Language Model (LLM) or a Knowledge Graph-based Model (KGM) to solve various Knowledge-based QA tasks in an episodic manner, based on historical data. The main goal is to achieve better performance at a lower cost throughout the entire QA process. This work formulates the problem as a multi-armed bandit problem and proposes a solution to this formulation.", "questions": "### Questions\n\n1. Do you just set the cost of KGM to 0? I cannot find the related details in the experiments section.\n2. In Figure 3, what is the difference between the three figures? Are they using different datasets?\n3. In Figure 4, what is the value of the y-axis? Is it k, the number of iterations? What dataset is each figure representing?\n\n### Suggestions\n\n- L265: \"While The\" should be corrected to \"While the\".\n- In Figure 4, the leftmost figure seems to have a typo in its y-axis label (000-1221 should be 1000-1221).", "limitations": "The authors already addressed the limitations in Section 6.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- **Originality:** The problem addressed is interesting. The approach of using multi-armed bandit problem formulation to decide between the efficient use of small models leveraging KG and the effective use of LLMs is novel. There appears to be no prior work addressing this specific problem.\n- **Quality:** The authors have appropriately formulated the problem and attempted to solve it using technically sound methods. The experimental results convincingly demonstrate the advantages of the proposed method.\n- **Significance:** This work is likely to inspire future studies in system cost optimization especially for LLMs. The experimental results highlight the potential to reduce costs while improving overall performance, which is impressive.", "weaknesses": "- **Clarity:**\n    - It is unclear if the cost in the experimental results is solely based on the number of times the LLM is used, with KGM usage considered cost-free. Additionally, the cost associated with using models like RoBERTa for Context-aware expert distinguishing, as discussed in Section 3.3, is not addressed in the experiments. Ignoring these local model costs might not be appropriate, and related discussions should be included in the experiments section.\n    - The specifics of the dataset usage are also unclear. The results in Table 1 seem to imply that KGM's arm embedding was updated using fine-tuned train data and then tested directly on test data, but the experimental setup isn't clearly explained.\n- **Significance:** There are questions regarding the practical applicability of the proposed method. The QA datasets used in the experiments are multiple-choice QA datasets, making accuracy measurement straightforward and benefiting from extensive research on KG-based models. However, applying this method in real-world applications like chat-bots poses challenges that need to be addressed. Despite this, the research lays a foundation for practical follow-up studies, which is a positive aspect.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to sincerely express our gratitude for your encouraging support and strong recognition, especially for your emphasis of our contribution to the community in the weakness again. We will carefully revise the final version following your suggestions.\n> Response to weaknesses\n- **W1: Clarity**.\nThanks for pointing this out, we will further clarify the setting in the revised version. In Section 2.2 Performance Evaluation, we introduced two metrics '**calls**' and '**API fees**', where calls (times) are used for evaluating our performance based on open-source LLMs and API fees (dollars\\$) are for GPT series. In auto-ML research, small models are considered to be free since they are far cheaper than big models like LLMs.\nFollowing your suggestions, we have also considered and quantified the cost of local KGMs and local LLMs through **`cloud service fee`** in dollars. Comparisons have been made over three domain-specific datasets uniformly with the API fees of GPT series, where in this case, our evaluation is more convincing now.\n**`cloud service fee`**: calculates the token-level cost based on basic requirements of GPU resources in one cloud server, instantiated by AWS g4dn.xlarge and p3.8xlarge with 0.526 USD and 12.24 USD per hour. \n\nwe have included two more metrics **`Inference Latency`** and **`Cost Advantage`** to comprehensively evaluate our performance. This also showcases that our evaluation can be general and followers can easily adapt to their own domain with specific evaluation metrics. We show the new results on three benchmark datasets as follows.\n**`Inference Latency (s)`**: the time used for making predictions in seconds.\n**`Cost Advantage (%)`**: used in HybridLLM-ICLR'24, as the percentage of questions answered by small models, while this metric is widely adopted for automatic ML.\n\n|                    |  Inference Latency (s)  | Cloud/API Fees ($) |  Inference Latency (s)  | Cloud/API Fees ($) |   Inference Latency (s)  | Cloud/API Fees ($) |\n|:------------------:|:-----------------------:|:------------------:|:-----------------------:|:------------------:|:------------------------:|:------------------:|\n|        HamQA       |          340.60         |        0.005       |          425.60         |        0.004       |          671.25          |        0.009       |\n|      GreaseLM      |          462.17         |        0.007       |          503.44         |        0.005       |          762.17          |        0.013       |\n|      Llama2 7B     |          61.20          |        0.20        |          60.00          |        0.20        |           61.20          |         0.4        |\n|      Llama3 8B     |          50.01          |        0.20        |          47.58          |        0.20        |           50.01          |         0.4        |\n|       GPT 3.5      |          26.33          |        0.05        |          27.29          |        0.02        |           26.33          |        0.15        |\n|        GPT-4       |          20.67          |        1.01        |          18.16          |        0.38        |           20.67          |        3.03        |\n|  Coke-HamQA (Ours) |          70.59          |       -20.16       |          58.25          |       -10.85%      |           46.12          |       -4.05%       |\n| Coke-Llama3 (Ours) |          36.22          |       -17.52%      |          25.37          |        -8.2%       |           30.41          |     **-41.92%**    |\n| Coke-Llama3 (Ours) | **CSQA Accuracy Imp%:** |       +2.48%       | **OBQA Accuracy Imp%:** |       +0.58%       | **MedQA Accuracy Imp%:** |       +3.26%       |\n\n| Cost Advantage (%) |  CSQA  |  OBQA  |  MedQA |\n|:------------------:|:------:|:------:|:------:|\n|  Coke-HamQA (Ours) | 20.89% | 11.02% |  4.32% |\n| Coke-Llama3 (Ours) | 18.62% |  9.70% | 48.55% |\n\n- **W2: Significance**.\nWe appreciate your expertise and believe this could help us further increase the impact within the community. To address your concerns, we would like to show our **`generalizability`** on two open-ended QA datasets, in addition to three original domain-specific multi-choice benchmarks.\n\n|           (Hits@1)           | WebQSP |  CWQ  |\n|:----------------------------:|:------:|:-----:|\n|            KV-Mem            |  46.72 | 18.51 |\n|           EmbedKGQA          |  66.60 | 45.35 |\n|            GrafNet           |  66.35 | 36.72 |\n|            GPT 3.5           |  65.30 | 41.50 |\n|             GPT-4            |  80.58 | 60.42 |\n|          Coke-EmbedKGQA (Ours)         |  **86.47** | **61.83** |\n| Cost Sav. ($ Cloud/API Fees) | **30.21%** | **3.45%** |\n> Response to questions and suggestions\n- **Q1: Cost of KGMs**.\nYes, as explained previously, small models are considered to be free in auto-ML since they are far cheaper than big models like LLMs. Following your suggestions, we have also considered and quantified the cost of local KGMs and local LLMs through **`cloud service fee`** in dollars\\$.\n- **Q2: Figure 3 clarification**.\nYes, three subfigures are drawn for CSQA, OBQA and MedQA respectively.\n- **Q3: Figure 4 clarification**.\nYes, axis-Y represents for the intervals of selection times. This case study observes the selection as k goes, which showcases the ability of our framework to balance exploration and exploitation (color changes from shallow->deep or deep->shallow). The datasets are for CSQA, OBQA and MedQA respectively.\n- **S1&S2: Typos**.\nThanks for your carefulness, we will fix the typos in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vXiwoRaTnw", "reviewer": "Reviewer_dW52", "summary": "1. This paper proposes a cost-efficient strategy named \"Coke\" to automatically assign the most promising model for particular questions.\n2. Experiments show the effectiveness of their method in Knowledge-based question answering (KBQA).", "questions": "See weakness", "limitations": "The authors discuss about the limitation of their work in one section.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The problem definition and mathematical explanation is clear.\n2. Experiments on 3 representative domain-specific datasets show the effectiveness of their method to improve performance and cost efficient.", "weaknesses": "1. As for the calls (times), I doubt it is a good metric because in generally users care more about call latency and commercial products always define token numbers to calculate price. (longer calls should have a larger price)\n2. Maybe not only LLM cost but also KGMs' cost should be considered\n3. 3 datasets are similar in the sense of reasoning, the generalizability is limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We gratefully thank you for your constructive comments which we believe will absolutely improve the quality of our paper. We also wish to invite you to check our new results with a more comprehensive consideration of evaluation metrics, cost of KGMs and generalizability.\n\n> Response to weaknesses\n* **W1: Evaluation metrics**.\nThanks for your constructive comments, we are inspired and have included two more metrics **`Inference Latency`** and **`Cost Advantage`** to address your concerns. Indeed, in our submission, we have already included two metrics '**calls**' and '**API fees**' , where calls are used for evaluating open-source LLMs and API fees are for GPT series. We show the new results on three benchmark datasets as follows.\n**`Inference Latency (s)`**: the time used for making predictions in seconds.\n**`Cost Advantage (%)`**: as the percentage of questions answered by small models, while this metric is widely adopted for automatic ML and used in HybridLLM-ICLR'24.\n\n|                    |  Inference Latency (s)  | Cloud/API Fees ($) |  Inference Latency (s)  | Cloud/API Fees ($) |   Inference Latency (s)  | Cloud/API Fees ($) |\n|:------------------:|:-----------------------:|:------------------:|:-----------------------:|:------------------:|:------------------------:|:------------------:|\n|        HamQA       |          340.60         |        0.005       |          425.60         |        0.004       |          671.25          |        0.009       |\n|      GreaseLM      |          462.17         |        0.007       |          503.44         |        0.005       |          762.17          |        0.013       |\n|      Llama2 7B     |          61.20          |        0.20        |          60.00          |        0.20        |           61.20          |         0.4        |\n|      Llama3 8B     |          50.01          |        0.20        |          47.58          |        0.20        |           50.01          |         0.4        |\n|       GPT 3.5      |          26.33          |        0.05        |          27.29          |        0.02        |           26.33          |        0.15        |\n|        GPT-4       |          20.67          |        1.01        |          18.16          |        0.38        |           20.67          |        3.03        |\n|  Coke-HamQA (Ours) |          70.59          |       -20.16       |          58.25          |       -10.85%      |           46.12          |       -4.05%       |\n| Coke-Llama3 (Ours) |          36.22          |       -17.52%      |          25.37          |        -8.2%       |           30.41          |     **-41.92%**    |\n| Coke-Llama3 (Ours) | **CSQA Accuracy Imp%:** |       +2.48%       | **OBQA Accuracy Imp%:** |       +0.58%       | **MedQA Accuracy Imp%:** |       +3.26%       |\n\n| Cost Advantage (%) |  CSQA  |  OBQA  |  MedQA |\n|:------------------:|:------:|:------:|:------:|\n|  Coke-HamQA (Ours) | 20.89% | 11.02% |  4.32% |\n| Coke-Llama3 (Ours) | 18.62% |  9.70% | 48.55% |\n\n* **W2: Cost of KGMs**\nThanks very much for the inspiration, following your suggestions, we have also considered and quantified the cost of local KGMs and local LLMs through **`cloud service fee`** in dollars. Comparisons have been made over three domain-specific datasets uniformly with the API fees of GPT series, where in this case, our evaluation is more convincing now. For details, please check the previous weakness for new results.\n**`cloud service fee`**: calculates the token-level cost based on basic requirements of GPU resources in one cloud server, instantiated by AWS g4dn.xlarge and p3.8xlarge with USD 0.526 and USD12.24 per hour.\n* **W3: Generalizability**\nThanks for your constructive comments. We believe considering generalizability will definitely enhance the soundness of our paper and enlarge the impact to the community. To address your concerns, we would like to show our **`generalizability`** on two open-ended QA datasets, in addition to three original domain-specific multi-choice benchmarks. In this pipeline of setting, the models are not limited to providing answers with choices or under any pre-defined formats.\n\n|           (Hits@1)           | WebQSP |  CWQ  |\n|:----------------------------:|:------:|:-----:|\n|            KV-Mem            |  46.72 | 18.51 |\n|           EmbedKGQA          |  66.60 | 45.35 |\n|            GrafNet           |  66.35 | 36.72 |\n|            GPT 3.5           |  65.30 | 41.50 |\n|             GPT-4            |  80.58 | 60.42 |\n|          Coke-EmbedKGQA (Ours)         |  **86.47** | **61.83** |\n| Cost Sav. ($ Cloud/API Fees) | **30.21%** | **3.45%** |", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
General Response
We would like to sincerely thank all the reviewers for their valuable comments. We are also very excited to be highly acknowledged for our **`contributions`** and **`significance`** to future studies in a variety of communities. To address the concerns raised by reviewers, we have correspondingly added a range of new experiments, which we believe has made our approach much more comprehensive and convincing.

We wish to invite all reviewers to check our new results and observations, which will all be added in the final revised version:
1. We have additionally included 2 more metrics to evaluate our performance in terms of cost saving: **`Inference Latency`** (inspired by Reviewer HDrN and dW52) and **`Cost Advantage`**(inspired by Reviewer FvaD and HybridLLM-ICLR'24), while originally we already have '**calls**' for local LLMs and '**API fees**' for GPT series in the submission (now in total 4 metrics). This also showcases that our evaluation can be general and followers can easily adapt to their own domain with specific evaluation metrics.
2. We have also considered and quantified the cost of local KGMs and local LLMs through **` cloud service fee`** in dollars instantiated by AWS g4dn.xlarge and p3.8xlarge (inspired by Reviewer JWNj and dW52). Comparisons have been made over three domain-specific datasets uniformly with the API fees of GPT series, where in this case, our evaluation is more convincing now.
3. We further show our **`generalizability`** on two open-ended QA datasets (inspired by Reviewer JWNj and dW52) , in addition to three original domain-specific multi-choice benchmarks.
4. We have demonstrated more comparison results with different base model combinations and heuristic baselines.
5. Four pseodu-codes are provided to demonstrate the algorithm for our main framework, Thompson Sampling and MAB (inspired by Reviewer HDrN and FvaD).

Thank again for all reviewers' suggestions that have greatly improved our paper. For specific details, please kindly check the corresponding responses and the PDF.

Meta-review: The paper proposes a novel strategy to optimise cost and accuracy in Question Answering (QA) tasks by dynamically switching between Large Language Models (LLMs) and Knowledge Graph-based Models (KGMs). This paper makes a solid contribution to the field of QA by proposing practical method for optimising cost and accuracy. 

Generally, the reviews for this paper are positive: the authors have provided responses to the reviewers' concerns resulting in some score increases. Authors have clarified the implementation details and addressed the issue of evaluating costs by introducing new metrics and considering the cost of KGMs. There are several weaknesses, although the authors have provided reasonable responses:

* The initial submission lacked details regarding models used, the training process, and the exact formulation of cost functions. The authors have acknowledged this and plan to provide more details in the revised version.
* While the use of Thompson Sampling is justified, the paper could benefit from a more thorough explanation of why it is the most suitable choice for this setting.
*  Although the method shows promise, the actual cost savings achieved are somewhat lower than expected, particularly in the MedQA dataset. There is probably room for improvement in the decision-making model.
* The effectiveness heavily depends on the performance of the KGMs, which may limit its generalisability in scenarios where KGMs are less effective.

I would also suggest to the authors that tangential work studying cost-aware policy orchestration in LLMs could be another method to compare against in future papers: https://arxiv.org/pdf/2401.13979v1
Decision: Accept (poster)