Dear Reviewer t5Eo,

Thanks a lot for your detailed feedback. We really appreciate your time and effort in pointing out the potential concerns related to our paper, and also, thanks a lot for the opportunity to further clarify the motivation, contribution, and technical details of our framework.

Regarding W1: Training and Implementation Details.

A: Thank you for your valuable feedback. We appreciate your perspective on the core ideas presented in our paper. And also, thank you for the valuable opportunity to clarify the details and contribution of our framework.

Two-stage training

The training of our model consists of two steps:

• We fisrt train an RL-based knowledge extraction model based on question-answer pairs in the training set, obtaining a well-trained policy network for knowledge extraction. After this stage, given a specific question, we can extract knowledge from the KG using two methods: RL-based policy network and the rule-based subgraph extraction method defined in Section B.1 of the Appendix.
• We can obtain two sets of raw knowledge for each question by applying these two knowledge extraction methods (RL-based policy network and rule-based subgraph extraction). To transform this structured raw knowledge into easily understandable text for LLM, we design three different prompt templates for knowledge transformation. To automatically select the most suitable combination to construct the final prompt for LLMs, we trained a MAB model based on the data in the training set.

After that, given a new question in the test set, we can automatically get the most suitable prompt in the text format based on the well-trained RL-based policy network and MAB model as follows.

For path extraction:

• Dataset: We extract the topic and choice entities from the original QA dataset. For each path, the source is set as the topic entity and the labeled target is the corresponding choice entity.
• Training: In Section C.6 of the Appendix, we elaborate on the details of using the policy gradient to train our policy.
• Evaluation: The overall path extraction performance is evaluated based on the cumulative rewards that the policy eventually obtains.

For MAB:

• Dataset: (1) We prepare the candidate paths based on two knowledge extraction methods for each arm (RL-based and subgraph). (2) We also prepare three candidate prompt templates for each path. In general, we have six combinations: 2 raw knowledge * 3 prompt templates. (3) An online LLM for the feedback, 1/0, to indicate whether the constructed prompt is effective.
• Training: Given a specific question, we train the MAB model based on the MSE loss.
• Evaluation: The evaluation of whether the MAB made an effective selection is based on the feedback from LLM during the testing phase. We use the overall accuracy as the evaluation metrics.

Regarding W2 (Q1,Q4): Compared to Deeppath and AEKE

A: We appreciate the reviewer's insightful comments and the opportunity to clarify the distinctions between our work and the cited papers. While our approach does involve searching for subgraph structures and prompt forms, we believe our contributions extend beyond just a search algorithm. Nevertheless, we acknowledge the importance of distinguishing our work from previous research.

• Compared to Deeppath:

  • The task is diferrent. DeepPath focuses on extracting a path from KG given start and end nodes. In contrast, our work addresses knowledge-based retrieval, extracting question-related knowledge while considering both KG structure and question semantics.
  • Reward function. DeepPath's reward function is primarily based on KG structure, considering accuracy, path efficiency, and diversity. Our RL model introduces a more comprehensive reward scheme that promotes reachability, context-relatedness, and conciseness of the extracted knowledge.
  • Traing strategy. While DeepPath uses supervised policy learning, our approach employs Gradient Clipping to maximize the expected cumulative reward, as detailed in Section C.6 of the Appendix. This difference in training strategy allows our model to better adapt to the complexities of knowledge-based question answering.

• Compared to AEKE: Our MAB approach differs from AEKE's significantly in training: we've introduced a penalty term, β, to encourage exploration of under-explored prompt formats. This modification allows for a more balanced exploration-exploitation trade-off, which is crucial in our context of selecting optimal prompt forms. We show the performance comparison between with and without this term hereunder.

Regarding Q2: Prompt Design

A: Generally, based on the complexity of the reasoning background, questions can be roughly categorized into three classes. Different types of questions correspond to different reasoning background. For example, simple questions only require basic facts in the form of triples, while multi-hop reasoning questions need a reasoning chain, and global reasoning questions require a more complex tree/graph-like reasoning background. To this end, we specifically designed three different prompt templates, including $\mathcal{F}_t$, $\mathcal{F}_s$, and $\mathcal{F}_g$, gudiding the LLM to convert the extracted raw knowledge into textual prompt with corresponding logical reasoning strucure as shown in Section 3.2.1 and C.6.

Regarding Q3: Definition of OLS and $\delta$

A: Sorry for the confusion. OLS is the ordinary least square loss. While $\delta$ is a constant, for any $\delta > 0$ with the probability at lease $(1-\delta)$, the reward expectation $E(.)$ is bounded by a confidence interval. We'll include the detailed description in our revision.

To verify the effectiveness of prompt formats, we conducted a statistical analysis on the benchmark datasets in terms of question types and then separately calculated the accuracy of different prompt formats on specific types of questions. As shown in Table 3, we can observe that triple-based prompt $\mathcal{F}_t$ performs best on simple questions, sentence-based prompt $\mathcal{F}_s$ work better for multi-hop questions while graph description-based prompt $\mathcal{F}_g$ performs better than any other prompt formats on complex questions. This is because graph description-based prompt could provide LLMs with more detailed and structured information by highlighting the local structure of the central entity.

[Q3] On line 212 of the 6-th page, what does OLS refer to? Does it mean Ordinary Least Squares? What does $\delta$ on line 218 of the sixth page refer to, is it a constant?

Thanks for your careful review. OLS is the ordinary least square loss. While $\delta$ is a constant, for any $\delta > 0$ with the probability at lease $(1-\delta)$, the reward expectation $E(r^{(i,b)} | {\bf x}_{i}^{(b)})$ is bounded by a confidence interval, as shown in h.

Thanks for your time and effort in providing insightful suggestions that can help further polish our paper. We're more than happy to provide any additional information or explanations that may be helpful in your review process.

[W2-a & Q1-c,d] The RL algorithm is fundamentally similar to Deeppath[1], and the authors should further distinguish the differences between them. Given that the action space in reinforcement learning on Knowledge Graphs is huge, how have you addressed this issue? From a technical solution perspective, what are the differences between the method 3.2 Knowledge Extraction with Deep Reinforcement Learning proposed in this paper and Deeppath[1]?

We appreciate the reviewer's insightful comments and the opportunity to clarify the distinctions between our work and the cited papers.

Differences compared to Deeppath:

• Motivation. DeepPath focuses on extracting a path from KG given start and end nodes. In contrast, our work addresses knowledge-based retrieval, extracting question-related knowledge while considering both KG structure and question semantics.
• Reward function. DeepPath's reward function is primarily based on KG structure, considering accuracy, path efficiency, and diversity. Our RL model introduces a more comprehensive reward scheme that promotes reachability, context-relatedness, and conciseness of the extracted knowledge. Especially, the context-relatedness encourages paths closely related to the given question context, which can help the RL agent reduce the search space since it can help filter out the irrelevant neightbors when considering the next step.
• Traing strategy. While DeepPath uses supervised policy learning, our approach employs Gradient Clipping to maximize the expected cumulative reward, as detailed in Section C.6 of the Appendix. This difference in training strategy allows our model to better adapt to the complexities of knowledge-based question answering.

[W2-b & Q4] Additionally, the authors should also elaborate on how the search algorithm proposed in this article differs from AEKE[2]. From a technical solution perspective, what is the difference between the content of Section 3.2 and the Active Ensemble Policy Learning with MAB described in AEKE[2]?

Thanks for the insightful comments. Our MAB approach differs from AEKE's significantly in training: we've introduced a penalty term, β, to encourage exploration of under-explored prompt formats. This modification allows for a more balanced exploration-exploitation trade-off, which is crucial in our context of selecting optimal prompt forms. We show the performance comparison between with and without this term hereunder.

Table 2: Ablation study on penalty term used in MAB-base prompt construction.

[Q2] What is the difference between "Graph Description" and "Sentences" in the prompt? Is the extracted subgraph structure the same for both, with the difference being that the "Graph Description" contains additional noise, such as "The entity is strongly associated with significant individuals in the tech industry."?

Thanks for raising this point. Existing methods rely on manually designed or rule-based prompts to present factual knowledge from KGs. These hard prompts are inherently inflexible and rigid, lacking the adaptability to accommodate variations in question semantics and KG structures. To this end, we designed three different prompt templates, including $\mathcal{F}_t$, $\mathcal{F}_s$, and $\mathcal{F}_g$, gudiding the LLM to convert the extracted raw knowledge into textual prompt with corresponding logical reasoning strucure. An MAB is trained to automatically select the most effective prompt template for each question.

The rationale behind our prompt design

Generally, based on the complexity of the reasoning background, questions can be roughly categorized into three classes: (1) Simple question, like “What could be used as an electrical conductor?”. (2) Multi-hop reasoning question, like “Which school did Bill Gates' wife graduate from?” (3) Global reasoning questions: “What do cats have in common with most mammals?”

Different types of questions correspond to different reasoning background. For example, simple questions only require basic factual triples, while multi-hop reasoning questions need a reasoning chain, and global reasoning questions require a more complex tree/graph-like reasoning background. To convert the extracted raw knowledge into textual prompt with corresponding logical reasoning structure, we designed three different prompt templates, including $\mathcal{F}_t$, $\mathcal{F}_s$, and $\mathcal{F}_g$.

Experimental analysis

Table 3. Accuracy of prompt templates on specific types of questions.

Dear Reviewer t5Eo,

We really appreciate your recognition of our work, and also appreciate your time and effort in providing insightful suggestions that can help further polish our paper. To make it clear, we provide more detailed responses to your comments and suggestions as follows:

[W1-a & Q1-a,b] How the reinforcement learning part on the knowledge graph is trained? On line 185 of the 5-th page, where are the additional training details mentioned in the appendix? Policy gradient is merely an algorithm, but how is the Agent on the Knowledge Graph trained?

Thanks for your question. We appreciate your interest in the training details of our model. In our submission, we focused on describing how we carefully designed a meaningful reward function to ensure that the RL model captures effective and informative knowledge, and the training detail is introduced in Section C.6 of Appendix.

To be clear, the policy network is updated using gradient-based optimization to maximize the expected cumulative reward. To stabilize the training of the policy network, we applied gradient clipping [1] to prevent the gradients from becoming too large. This technique helps mitigate the problem of exploding gradients and ensures stable updates of the network parameters. To demonstrate the effectiveness of gradient clipping, we conducted additional experiments comparing the performance of our model with and without gradient clipping across five runs. The results are presented in Table 1 below (you can also find the results in Table 10 of our original submission).

Table 1: Abliation study for gradient clipping.

As shown, the model with gradient clipping consistently achieves better performance across all datasets, demonstrating the stability and robustness of our method.

[W1-b] How to optimize the Knowledge Graph Agent together with the Prompt Construction with Multi-armed Bandit as proposed in Section 3.2?

Thanks for the insightful comments. Ideally, we would like to design a end-to-end model: Given a LLM and a domain knowledge graph, the RL model could search from the KG to find the most concise, relevant, and informative knowledge according to the feedback from the LLM. This knowledge is then provided to the LLM to help it accurately answer professional questions. However, training such an RL model is extremely costly. Since RL-based knowledge retrieval is a Markov Decision Process, the RL agent would need feedback from the LLM at each decision step during training, requiring frequent interactions with the LLM and incurring huge API costs.

To reduce the API cost, in this paper, we proposed a two-stage model, splitting the goal into two steps.

• Knowledge extraction, which aims to extract the most relevant and informative knowledge from the knowledge graph for the target question. We designed three rewards to ensure that the RL model extracts correct, concise, and effective background knowledge.
• Prompt Construction. It designs three different prompt templates for different questions and convert the extracted raw knowledge into a form that the LLM can most easily understand based on the LLM's feedback.

The two-stage model can greatly reduce the API cost because we only need to interact with the LLM in the second stage.

Back to your concern, the training of our model consists of two steps:

• We fisrt train an RL-based knowledge extraction model $P_{RL}$ based on question-answer pairs in the training set, obtaining a well-trained policy network for knowledge extraction. After this stage, given a specific question, we can extract knowledge from the KG using two methods: RL-based policy network $P_{RL}$ and the vanilla rule-based subgraph extraction $P_{sub}$ defined in Section B.1 of the Appendix.
• We can obtain two sets of raw knowledge for each question by applying these two knowledge extraction methods ($P_{RL}$ and $P_{sub}$). To transform this structured raw knowledge into easily understandable text for LLM, we design three different prompt templates for knowledge transformation. Therefore, we have six combinations: two raw knowledge * three prompt templates. To automatically select the most suitable combination to construct the final prompt for LLMs, we trained a MAB model based on the data in the training set.

After that, given a new question in the test set, we can automatically get the most suitable prompt in the text format based on the well-trained RL-based policy network and MAB model.

[W1-c] As for the two-hop subgraph extraction, the paper does not provide implementation details for the proposed method.

Thanks for your insightful feeadback. We include the implementation details of the vanilla 2-hop subgraph extraction $P_{sub}$ in Section B.1 of the Appendix. To make it more clear, we will first explain the rationales behind the design of two knowledge extraction methods before summarizing the implementation details of $P_{sub}$.

The rationale behind knowldge extraction methods.

If the background knowledge graph is complete and high-quality, our proposed RL-based knowledge extraction $P_{RL}$ can ideally handle all cases. But in practical implementation, we found that there are a few long-tail entities in KGs which only have few neighbors. In such cases, RL-based path extraction can hardly retrieve reachable or effective paths due to the incompletion and sparsity of the background graph. Instead, directly extracting the whole subgraph through rule-based subgraph extraction can provide more effective knowledge. RL-based retrieval method $P_{RL}$ could make sure our model extract more concise and informative knowledge in most case, while the rule-based subgraph extraction $P_{RL}$ could supplement the former especially when the reasoning background is sparse.

Thus, in this paper, we adopt Multi-Armed Bandit (MAB) to automatically select the most suitable retrieval methods from these two candidates, i.e., $P_{RL}$ and $P_{sub}$.

Experimental analysis of knowldge extraction methods.

The ablation study on knowledge retrieval method can be found in Table 3 of our submission. Specifically, we compare our model with $P_{RL}$, the heuristic sub-graph extraction $P_{sub}$, and we also include ‘w/o KG’ as the baseline where the LLM is asked to independently answer the given question with no reasoning background provided. The results shown in Table 3 of our submission clearly indicate the vital role of our proposed path extraction strategies.

Implementation details of $P_{sub}$.

Due to page limits, we include the implementation details of the vanilla 2-hop subgraph extraction $P_{sub}$ in Section B.1 of the Appendix. Specifcally, we commence by executing entity linking on $\mathcal{G}$, resulting in an initial collection of nodes, $V_{topic}$. Next, we incorporate bridge entities that appear within a 2-hop path between any two linked entities from $V_{topic}$, yielding the set $V_{retrieval}$. After that, we refine this set by evaluating the relevance score for each node, following the previous study[1]. From this refined set, only the top 200 nodes, based on score, are retained. We extract all edges connecting any pair of nodes in $V_{sub}$, creating the retrieved subgraph $G_{sub}$. Each node within $G_{sub}$ is designated a type based on its association to either the topic entities $Q$ or target entities $A$.

[W1-d] For LLMs, is it a multi-class or multiple binary (as in the YES/NO from Figure 2) classification problem? With multiple binary classifications, there is the issue of handling multiple (or zero) options being YES—how should this be dealt with? (Situations with all NO or all YES responses may arise.)

Thank you for making this valuable question. In this paer, we evaluate KnowGPT on three multi-choice QA datasets spanning two fields: CSQA and OBQA serve as benchmarks for commonsense reasoning, while MedQA acts as a domain-specific QA benchmark. Given the quesion with several choices, we let LLM give the specifc answer, like A/B/C/D, by providing it with background knowledge about the source entities from the original question and the target entities from all candidate choices. This approach transforms the task into a decision-making problem since we provide the LLM with comprehensive background knowledge for all candidate choices simultaneously, allowing it to make informed decisions based on a holistic view of the available information.

Dear Reviewer t5Eo,

Thank you for your recognition of our work and for providing such thorough and insightful feedback. We greatly appreciate the time and effort you've invested in reviewing our work and providing such detailed comments. Your comments and suggestions are invaluable in helping us improve the quality and clarity of our work.

We have carefully considered each point you raised and have made substantial analysis and explanation. If there are any aspects that you feel still require further clarification or improvement, we would be more than happy to provide additional information or explanations to assist in your review process.

Thank you again for your time and expertise. Your feedback has been instrumental in enhancing the quality of our research.

Dear Reviewer vKLu,

We really appreciate your recognition of our work, and thanks a lot for providing insightful suggestions that can help further polish our paper.

Regarding W1 (Q1,Q2): Efficiency Analysis

A: Thank you for the constructive comments. To make it more clear, we will first introduce the training and implementation details of our model before the detailed efficiency analysis.

Model Training

Ideally, we would like to design a end-to-end RL model: Given a LLM and a domain knowledge graph, the RL model could search from the KG to find the most concise, relevant, and informative knowledge according to the feedback from the LLM. This knowledge is then provided to the LLM to help it accurately answer professional questions. However, training such an RL model is extremely costly. Since the RL agent would need feedback from the LLM at each decision step during training, requiring frequent interactions with the LLM and incurring huge API costs.

To reduce the API cost, in this paper, we proposed a two-stage model. The first step aims to extract the most relevant and informative knowledge from the knowledge graph for the target question, and the second step is to design three different prompt templates for different questions and convert this raw knowledge into a form that the LLM can most easily understand based on the LLM's feedback. The two-stage model can greatly reduce the API cost because we only need to interact with the LLM in the second stage (prompt design).

Efficiency analysis

Back to your concern, to investigate the efficiency of our model, we compare it on MedQA with 4 representative baselines from two different categories, including traditional KG-enhanced LMs and the SOTA KG-prompting-based LLMs, i.e., CoK and Mindmap.

From Table 1, we can see that:

• Traditional KG-enhanced LM methods, like JointLK and GrapQA, have the shortest inference time. This is because the other models need to send requests to the LLM via API, and the extra response time of the LLM leads to long inference times for these models. Despite the efficiency, they have the worst performance.
• Our model outperforms the other models with comparable training time and the most economical API cost compared to models in the same category, including CoK and Mindmap. That is because we are the only model that consider the conciseness of knowledge during retrieval and prompt design.

Table 1. Efficiency analysis on MedQA.

Regarding W2: Overlong Introduction

A: Thanks a lot for the valuable suggestion. We’ll condense the introduction section by highlighting the key idea of our model.

Regarding Q2: Laborious Prompt Design

A: Existing methods rely on manually designed or rule-based prompts to present factual knowledge from KGs. These hard prompts are inherently inflexible and rigid, lacking the adaptability to accommodate variations in question semantics and KG structures. To this end, we specifically designed three different prompt templates, including $\mathcal{F}_t$, $\mathcal{F}_s$, and $\mathcal{F}_g$, gudiding the LLM to convert the extracted raw knowledge into textual prompt with corresponding logical reasoning strucure. An MAB is trained to automatically select the most effective prompt template for each question.

The rationale behind our prompt design

Generally, based on the complexity of the reasoning background, questions can be roughly categorized into three classes as defined in Section C.3. Different types of questions correspond to different reasoning background. For example, simple questions only require basic factual triples, while multi-hop reasoning questions need a reasoning chain, and global reasoning questions require a more complex tree/graph-like reasoning background.

Table 2. Accuracy of prompt templates on specific types of questions.

As shown in Table 2, triple-based prompt $\mathcal{F}_t$ performs best on simple questions while graph description-based prompt $\mathcal{F}_g$ performs significantly better than any other prompt formats on complex questions. It is because graph description-based prompt could provide LLMs with more detailed and structured information by highlighting the local structure of the central entity.

Regarding Q3: Proportional Distribution

A: Thank you for your valuable suggestion. We have conducted a thorough analysis on three benchmark datasets.

Table 3. Proportional distribution of different knowledge extraction methods and prompt form on three datasets.

From the table 3, we can see that:

• Our RL-based knowledge extraction approach $P_{RL}$ was consistently favored across all datasets, which verifies the ability of model to find complex reasoning paths.
• The distribution of prompt forms varied more across datasets. The triple format were most prevalent in both CSQA and OBQA, likely due to there are lots of simple questions in these two datasets that the LLM could easily answer them with simplest knowledge format.
• Graph descriptions were used least frequently overall, but still played a significant role, especially in MedQA (25.78%).

Dear Reviewer vKLu,

We are deeply grateful for your strong support and for raising the confidence score. Your insightful suggestions are crucial in elevating the quality of our paper. We'll incorporate all the additional experiments and analysis in our final revision. Thank you for your time and expertise throughout this review process.

Dear reviewer 4L5K,

Thanks a lot for your detailed feedback. We really appreciate your recognition of our work and also appreciate your time and effort in providing insightful suggestions that can help further polish our paper. Below are detailed responses to your comments and suggestions:

Regarding W1: Move Case Study into Main Paper

Thank you for your valuable suggestion. Due to page limits, we included the efficiency analysis, case study, ablation study and some supplementary results in the Appendix. Following your advice, we’ll move the key contents, like the case study, into the main paper.

Regarding Q1: Impact of Entity Extraction Model

Thanks for the insightful comments. In this paper, we focused on developing effective and efficient knowledge retrieval and injection methods, assuming entity extraction as a separate step to isolate the impact of our core contributions. Specifically, in the original paper, we assume that the source and target entities are given by using BERT as the default entity recognition model. Actually, discussing the impact of using an off-the-shelf model for entity extraction is valuable to speed up real-world applications of our method. We thank the reviewer for bringing this important point to our attention.

To investigate the effect of entity recognition model, we conducted an additional experiment on the CSQA dataset to evaluate the impact of using off-the-shelf entity recognition models.

Table 1. Comparisons of entity recognition model on CSQA.

Due to time limit, we only replace the BERT used in our model with the most advanced entity recognition model, Llama2-7B and Llama3-8B. As shown in Table 1, we can see that most state-of-the-art entity recognition models achieve high accuracy (>90%) on this task. The performance of our method can be further improved by applying more advanced entity recognition models, like Llama2-7B and Llama3-8B.

We thank the reviewer for bringing this important point to our attention. We will add these experiments and discussion in our revised version.

• Efficiency Analysis. Existing KG prompting methods often suffer from the huge API cost. To investigate the efficiency of our model, we compare it on MedQA with several SOTA baselines in terms of both API cost and training efficiency. The results can be found in Table 9 of our submission and Table 1 of the Rebuttal to Reviewer vKLu.

• Prompt Design. The hard prompts used in existing KG prompting models are inherently inflexible and rigid, lacking the adaptability to accommodate variations in question semantics and KG structures. To this end, we specifically designed three different prompt templates, guiding the LLM to convert the extracted raw knowledge into textual prompt with corresponding logical structure. To make it clear, we first carefully explained the rationale behind our prompt design and then introduced the implementation details (the Rebuttal to Reviewer vKLu and t5Eo) following with a detailed experimental analysis (Table 1 of the Rebuttal to Reviewer vKLu).

• Proportional Distribution. To verify the effect of the MAB-based prompt constriction strategy, we conducted a thorough analysis on three benchmarks (Table 3 of the Rebuttal to Reviewer vKLu) by investigating the proportional distribution of different knowledge extraction methods and prompt forms during testing.

• Implementation Details. In our submission, we focused on describing how we carefully designed a meaningful reward function to ensure that the RL-based extraction model $P_{RL}$ captures effective and informative knowledge, and the implementation details are included in the Appendix. Specifically, we introduced the details of sub-graph extraction strategy $P_{sub}$ in Section B.1, while the training details of RL model are included in Section C.6 of Appendix. To make it clear, we first explained the rationales behind the design of two knowledge extraction methods and then summarized the training details together with several supporting experiments (Table 1 of Official Comment to Reviewer t5Eo and Table 3 of our submission). We'll include a new Algorithm 1 in our revision to show the overall training process.

• Differences Compared to Deeppath and AEKE. We clarified the differences between our work and the cited papers in both the Rebuttal and Official Comment to Reviewer t5Eo. Specifically, our model diverges from DeepPath in motivation, reward function and training strategy, while our MAB approach differs from AEKE's significantly in training since we introduced a penalty term to encourage exploration of under-explored prompt formats. To make it more clear, we included additional experiments to verify the effect of our tailored design (Table 1&2 of Official Comment to Reviewer t5Eo).

Thank you again for your time and expertise throughout this review process. We deeply appreciate your expertise and recognition of our work. Each point raised has given us new perspectives to consider. We commit to addressing all the comments and incorporating the additional experiments and analysis in our final revision. Hope that this summary could facilitate the next stage of review and discussion.