Thank you for your valuable feedback and the time you have spent reviewing our work. We address the concerns raised and provide answers to your questions accordingly.

Response to Task Formulation 1

Thank you for your valuable feedback. We will address the questions and ensure clearer definitions of key concepts, notations, and dataset details in the revised version.

Surrounding context refers to textual outputs that do not contribute directly to reasoning but are generated to ensure natural language coherence. For example, in the sample shown in Figure 3 (Above - OCEAN Llama-3), the reasoning path is “playing guitar -$>$ singing.” When combined with the surrounding context, the sentence becomes: “Singing is a common activity that people do while playing guitar.” Here, phrases like “is a common activity that people do while” are not directly related to the reasoning process but are included to maintain fluency and coherence in natural language.

Response to Task Formulation 2

We acknowledge the inconsistency in our notation. To clarify, in line 169, $e_{t-1}$ should represent the current entity, not the edge. Throughout the rest of the paper, including Equation 3 and line 172, $e$ consistently represents an entity. We will revise line 169 accordingly.

Response to Methodology 1

Thank you for the suggestion! Here is an example from our method for your reference. We will also incorporate additional illustrative examples in the paper. In Wikidata5M, one such trajectory is: [“United States”, “contains”, “Arizona (state)”], where “United States” and “Arizona (state)” are the nodes, and “contains” represents their relationship. Following the verbalizing transformation, we generated the paragraph below, where answering the question requires knowledge of this trajectory:

The North Carolina division of the World Commission on North Carolina Geography (WCNG) is located within the North Carolina tourism department. The state of North Carolina is headed by its governor, Roy A. Cooper III, who is a member of the Democratic Party. North Carolina is a part of the United States of America, which is a democratic country. The state shares its boundaries with the state of Arizona in the United States. Based on the above context, ask a question about WCNG and whose answer should be exactly arizona (u.s. state). The question is: Which state shares its boundaries with North Carolina, as determined by the World Commission on North Carolina Geography (WCNG)? Provide the answer in 5 words:

Response to Methodology 2

We explore the knowledge graph by randomly sampling trajectories, which are then verbalized as described in Section 3.2. These verbalized trajectories are subsequently utilized in the KG-IPS estimator, which offers an unbiased estimate of the target policy and serves as a guide for the LLM fine-tuning process.

Response to Methodology 3

We provided detailed information about the offline dataset used for preference modeling and the implementation details in Section 5.1 (Line 322 - 327). The offline dataset comprises 6K sampled trajectories from the knowledge graph. We would provide further clarifications or additional details if needed.

Response to Methodology 4

As explained in Section 4.2, the preference policy is trained with the collected offline dataset using the policy gradient method in Line 273. Detailed training and implementation information is provided in Section 5.1 (Line 322 - 327). We would provide further clarifications or additional details if needed.

Response to Methodology 5

In this equation, $c$ represents the entire reasoning path, which consists of a sequence of tokens. $e$ denotes each individual token within this path. Since not all tokens are included in the knowledge graph trajectories, $a_t$ is used to represent the set of entity tokens. Thanks for pointing this out. The term $1/ c_t^{(i)}$ should be inside the second summation. Additionally, it should be written as $e \in c_t^{(i)}$. We will update the equation accordingly in our paper.

Response to Methodology 6

The reward function in our paper focuses on token-level rewards. Specifically, in the estimation of inverse propensity score (IPS), we need to calculate the ratio $\frac{\pi(e|s_t^{(i)})}{\lambda(e|s_t^{(i)})}$ measuring the entity-level alignment of taking action between the learning and logging policies. Thus, we derive rewards for entity tokens using the knowledge graph preference policy $\mu_\theta$, while rewards for non-entity tokens are based on the base LLM policy $\pi_0$. Such rewards on tokens instead of steps enable a more accurate estimation of IPS. In addition, fine-grained feedback or supervision maintains the LLM's generation ability and enables more controllable alignment [a,b,c,d]. The formulation in line 159 provides a more general reward function. Our reward function can be viewed as a specific case of the general reward, as it optimizes the policy based on token-level rewards.

Response to Minor suggestions

Thanks for the suggestions. We will include preliminaries about IPS and offline policy evaluation in our paper.

[a] Xu, Dehong, et al. "Aligning Large Language Models via Fine-grained Supervision." arXiv preprint arXiv:2406.02756 (2024).

[b] Yoon, Eunseop, et al. "TLCR: Token-Level Continuous Reward for Fine-grained Reinforcement Learning from Human Feedback." Findings of the Association for Computational Linguistics ACL 2024. 2024.

[c] Li, Wendi, et al. "Reinforcement Learning with Token-level Feedback for Controllable Text Generation." Findings of the Association for Computational Linguistics: NAACL 2024. 2024.

[d] Zeng, Yongcheng, et al. "Token-level Direct Preference Optimization." Forty-first International Conference on Machine Learning.

Thank you for your valuable feedback and the time you have spent reviewing our work. We address the concerns raised and provide answers to your questions accordingly.

Response to Weakness 1

Thanks for pointing this out. We will fix this and make sure all abbreviations used are defined in their appearance.

Response to Weakness 2

Thanks for the suggestion. We added an illustrative figure in Appendix D (i.e., Figure 4) to demonstrate the evaluation pipeline to better explain the workflow.

Response to Weakness 3

The intuition behind defining this term after the third summation symbol is inspired by the Inverse Propensity Score (IPS) , which is widely used in reinforcement learning for off-policy evaluation to estimate the expected reward of a target policy $\pi_\theta$ using data collected from a different behavior policy. Here, $c$ represents the entire reasoning path, and $e$ denotes each token within the path. The log-likelihood score of each token under the base policy $\pi_0$ is used as the reward function. The term before the reward serves as a weighting factor to adjust the mismatch between the target policy $\pi_\theta$ and the behavior policy.

Due to the reason that not all tokens are included in the KG trajectories, the calculation is two-fold.

1. For entity tokens, the reward is derived under the knowledge graph preference policy $\mu_\phi$, which serves as the behavior policy for these tokens.
2. For non-entity tokens, the reward is based on their likelihood under the base language model policy $\pi_0$. This can also be considered as a regularization term in the reward function. We then compute the sum of rewards for all tokens and normalize it across $T$ iterations.

Response to Weakness 4

The x-axis in Figures 1(b) and 1(c) represent the indices of sampled relations and entities ordered by their respective frequencies of appearance in the trajectories.

Figures 1(b) and 1(c) illustrate the distribution of sampled relations and entities. The x-axis represents the relations and entities, ordered by their respective frequencies of occurrence in the trajectories, from the most frequent to the least frequent. For instance, in Figure 1(b), the most frequent relation appears over 1,200 times, while the second most frequent relation occurs approximately 500 times. As mentioned in Lines 275–280, we observe that the distribution of relations is notably skewed, with a stronger emphasis on the most frequent relations.

Response to Weakness 5

Since verbalization of knowledge graph reasoning is not the major contribution of OCEAN, we follow the standard model architectures in previous works [a,b,c] for reference modeling. To further understand the performance of the reference models of different architectures, we train the reference model based on GPT-Base, GPT-Medium, and GPT-XL. With different reference models, we evaluate both the base LLMs and OCEAN of Llama-3, Gemma-2, Phi-3.5, and Mistral-0.2.

We observe that with different architectures used for reference models, although the estimation scale $\hat{V}(\theta)$ slightly differs due to the log probability scales from the output space of each model, there is a consistent improvement in the alignment of OCEAN across different backbone LLMs.

Response to Weakness 6

The answer accuracy in Figure 1(a) is used as a metric for (Line 258 - 269) sampling quality control to filter out unreasonable trajectories, which are used for the development of the reference model. During policy evaluation and optimization, the reference model provides weighting (In Equation 3) for every reward signal on each reasoning step in the process, which formulates the calculation of the inverse propensity score.

[a] Guan, Jian, et al. "A knowledge-enhanced pretraining model for commonsense story generation." Transactions of the Association for Computational Linguistics 8 (2020): 93-108.

[b] Andrus, et al. "Enhanced story comprehension for large language models through dynamic document-based knowledge graphs." In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, no. 10, pp. 10436-10444. 2022.

[c] Khorashadizadeh, Hanieh, et al. "Research Trends for the Interplay between Large Language Models and Knowledge Graphs." arXiv preprint arXiv:2406.08223 (2024).

Thanks for the reviewer's comment.

In Lines 258 - 269, we first randomly collect a set of trajectories (in Equation 2), which contain a list of triplets for each trajectory. Each triplet contains a subject entity, a relation, and an object entity. Secondly, to further measure the validity of the sampled knowledge graph trajectories in terms of serving as reasoning paths, we follow the conventional self-consistency measurement [1,2] to prompt the GPT-4 model to propose a question about the first token in the trajectory, whose answer should be the last token. Therefore, the verbalized knowledge graph trajectory can be used as the reasoning paths of the question-answering pair. Then, we prompt the GPT-4 model to evaluate that given the proposed question and the verbalized knowledge graph trajectory, how likely the GPT-4 model could accurately answer the question. Such self-consistency measurement results in Figure 1(a), where such QA accuracy probability is used as the reward function (in LIne 265) for each verbalized knowledge graph trajectory. Finally, in Line 274, the KG preference model is trained on the verbalized knowledge graph trajectories with the developed reward function.

We hope our response addresses your concerns. Please let us know if there are any additional questions, and we are happy to discuss further.

[1] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171, 2022b.

[2] Potsawee Manakul, Adian Liusie, and Mark JF Gales. Selfcheckgpt: Zero-resource black-box hallucination detection for generative large language models. arXiv preprint arXiv:2303.08896, 2023.

Thank you for your valuable feedback and the time you have spent reviewing our work. We address the concerns raised and provide answers to your questions accordingly.

Response to Weakness 1

As discussed in the Introduction (Line 38 - 47) and Related Work (Line 87 - 103), in general, offline policy evaluation and optimization are important, since online deploying the policy to interact with users can be risky, costly, and impractical [a,b,c], especially for LLMs [k,l]. Particularly in our setting, online policy optimization requires multi-step feedback on any possible generated sequences of thoughts, which is exhaustive and unrealistic to collect from humans in practice. Besides, human feedback on chain-of-thought reasoning [d] is usually challenging to collect, as detailed in Line 48 - 53 of our paper.

To enable online learning in the knowledge-intensive tasks that are the focus of our paper, we can potentially use the recent work [e] leveraging knowledge graphs to enable evaluating chain-of-thought. However, [e] is restrained to the assumption of accurate chain-of-thought grounding on specific knowledge graphs. Specifically, due to the heterogeneity between LLM reasoning and knowledge graph structures, direct interaction and feedback from knowledge graphs on LLM behavior are challenging, as they require accurate entity linking and grounding of LLM-generated chains of thought in the knowledge graph. To address the above challenge, we develop a verbalized knowledge graph reference model as detailed in Section 4.2.

Response to Weakness 2

Several recent works have leveraged knowledge graphs to align LLM reasoning [g,h,i,j] with more faithful multi-hop reasoning, which demonstrates the effectiveness and validity of evaluating LLM multi-step reasoning based on knowledge graphs. However, different from previous works focusing on retrieval augmentation [g,h] or knowledge injection [i,j], our paper focuses on calibrating LLM reasoning through offline policy evaluation and optimization.

Response to Weakness 3

As detailed in Line 257 - 280, the usage of GPT-4 is used as an instantiation and limited only to verbalizing structured knowledge graph trajectories into natural language, which is a standard approach in many knowledge graph-enhanced LLM generation methods [m,n,o,p].

During the self-consistent measurement process (Line 257 - 264), the generated question-answering pairs will not be used in LLM fine-tuning, but only for self-consistent sample filtering purposes (such that no extra knowledge is introduced during knowledge graph verbalization). We would like to emphasize that the contributions of our paper are the offline evaluation framework for LLM chain-of-thought generation, direct policy optimization method, and theoretical analysis of the proposed estimator, where the performance improvements come from the offline policy evaluation and optimization method.

Response to Question 1

Due to the heterogeneity between knowledge graphs and LLM reasoning forms (detailed in Line 60 - 64 of our paper), a Direct Method (DM) estimator trained on knowledge graphs cannot directly evaluate complex LLM-generated sequences of thoughts, which leads to limited reward feedback on multi-step reasoning paths and thus Direct Method (DM) also will be biased in estimation [f,q,r,s,t].

Intuitively, such heterogeneity can be addressed by the Equation in line 207 of our paper. the ratio $\frac{\pi(e|s_t^{(i)})}{\lambda(e|s_t^{(i)})}$ measures the entity-level alignment of taking an action between the learning and logging policies. Without considering this term, DM can not handle the heterogeneity.

Response to Question 6

The baseline SFT is just trained on the questions and answers. It is not practical/scalable to train SFT on reasoning steps, for the following considerations. First, it is not scalable to conduct SFT on the reasoning steps collected by humans. As mentioned in previous work [d,u,v] and in our paper (Line 48 - 53), human feedback on chain-of-thought reasoning is challenging to collect. Thus, it is not realistic to annotate an adequate amount of reasoning steps to conduct SFT in practice. Second, it is not feasible to conduct SFT on the reasoning step directly generated by the KG, considering the heterogeneity between LLM reasoning and knowledge graph structures. Instead, our approach aligns the models on the generated reasoning steps (without relying on the reasoning steps collected from humans), by bridging the above heterogeneity between knowledge graphs and LLM reasoning forms through IPS policy estimation.

Response to Question 2,3,4,5,7,8,9

Q2: The offline policy evaluation performance without performing updated according to equation 4 is exactly the reported Base performance in Table 1 and Table 2.

Q3 and Q8: The currently reported SFT performance is the performance of SFT + normal COT in Table 1, Table 2, and Table 3.

Q4: As detailed in Section 4.1, we explain the calculation of policy evaluation in Equation 3.

Q5: OCEAN and SFT are both fine-tuned based on the Base model.

Q7: Since the index k is for each question q and generated answer y, the equation for the policy gradient should be subscribed by k, i.e., $\mu_{\phi}(y_{k,t}|q_{k},y_{k,<t})$. We will edit this accordingly to avoid confusion.

Q9: Following the existing setting for knowledge-intensive and multi-hop question-answering (Line 293 - 310), we study the dual experimental settings where the LLM's prompt only contains the query (w/o ctx), and the relevant context of knowledge provided by the dataset is also included in the prompt (w/ ctx). We will better highlight such information in our experimental settings.

[a] Levine, Sergey, et al. "Offline reinforcement learning: Tutorial, review, and perspectives on open problems." arXiv preprint arXiv:2005.01643 (2020).

[b] Gilotte, Alexandre, et al. "Offline a/b testing for recommender systems." Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining. 2018.

[c] Jeunen, Olivier. "Revisiting offline evaluation for implicit-feedback recommender systems." Proceedings of the 13th ACM conference on recommender systems. 2019.

[d] Joshi, Nitish, et al. "Improving Multi-Hop Reasoning in LLMs by Learning from Rich Human Feedback." Neuro-Symbolic Learning and Reasoning in the era of Large Language Models. 2023.

[e] Nguyen, Minh-Vuong, et al. "Direct Evaluation of Chain-of-Thought in Multi-hop Reasoning with Knowledge Graphs." arXiv preprint arXiv:2402.11199 (2024).

[f] Dudík, Miroslav, John Langford, and Lihong Li. "Doubly robust policy evaluation and learning." arXiv preprint arXiv:1103.4601 (2011).

[g] Wu, Yike, et al. "CoTKR: Chain-of-Thought Enhanced Knowledge Rewriting for Complex Knowledge Graph Question Answering." Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. 2024.

[h] Sun, Jiashuo, et al. "Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph." The Twelfth International Conference on Learning Representations.

[i] Zhang, Yu, et al. "Question-guided Knowledge Graph Re-scoring and Injection for Knowledge Graph Question Answering." Findings of the Association for Computational Linguistics: EMNLP 2024. 2024.

[j] Fu, Peng, et al. "Revisiting the Knowledge Injection Frameworks." Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. 2023.

[k] Zhang, Shenao, et al. "Self-Exploring Language Models: Active Preference Elicitation for Online Alignment." Automated Reinforcement Learning: Exploring Meta-Learning, AutoML, and LLMs.

[l] Ding, Mucong, et al. "SAIL: Self-improving Efficient Online Alignment of Large Language Models." ICML 2024 Workshop on Theoretical Foundations of Foundation Models.

[m] Wang, Jianing, et al. "Knowledge Prompting in Pre-trained Language Model for Natural Language Understanding." Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. 2022.

[n] Fang, Tianqing, et al. "Complex reasoning over logical queries on commonsense knowledge graphs." arXiv preprint arXiv:2403.07398 (2024).

[o] Fu, Xiyan, and Anette Frank. "The Mystery of Compositional Generalization in Graph-based Generative Commonsense Reasoning." Findings of the Association for Computational Linguistics: EMNLP 2024. 2024.

[p] Wang, Zhichun, and Xuan Chen. "DERA: Dense Entity Retrieval for Entity Alignment in Knowledge Graphs." arXiv preprint arXiv:2408.01154 (2024).

[q] Liu, Anqi, Hao Liu, Anima Anandkumar, and Yisong Yue. "Triply robust off-policy evaluation." arXiv preprint arXiv:1911.05811 (2019).

[r] Dasgupta, Sutanoy, et al. "Off-Policy Evaluation Using Information Borrowing and Context-Based Switching." arXiv preprint arXiv:2112.09865 (2021).

[s] Farajtabar, Mehrdad, Yinlam Chow, and Mohammad Ghavamzadeh. "More robust doubly robust off-policy evaluation." International Conference on Machine Learning. PMLR, 2018.

[t] Shi, Chengchun, et al. "Deeply-debiased off-policy interval estimation." International conference on machine learning. PMLR, 2021.

[u] Xu, Weiwen, et al. "Exploiting Reasoning Chains for Multi-hop Science Question Answering." Findings of the Association for Computational Linguistics: EMNLP 2021. 2021.

[v] Zhao, Wenting, et al. "Hop, Union, Generate: Explainable Multi-hop Reasoning without Rationale Supervision." Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. 2023.

I would like to thank the reviewer for their response and would like to ask a few follow-up questions and clarification questions.

Follow-up to Question 6: I assume this paper addresses the issues related to scaling human preference data by utilizing knowledge graph preferences instead. Specifically, you convert chains of triplets from the knowledge graph into chains of thoughts using a model f to verbalize them. This suggests that you have a computational oracle (i.e., a verbalizer) rather than a human oracle to query, correct? If this is the case, then you are not relying on human feedback for reasoning chains and can actually scale beyond the limitations associated with human preferences.

Yes, papers [d, u, v] mentioned that collecting human preference on the chain of thoughts is challenging, which I agree with. However, all of those papers include SFT-related experiments on their respective chain of thought datasets. In particular, [d] discusses how fine-tuning on small datasets with rich human feedback can improve model performance, while [u] presents a supervised training baseline where they directly train using the reasoning chain.

In the context of this paper, I agree that the heterogeneity between LLM reasoning and knowledge graph structures is a problem. However, you address this issue by using an LLM to verbalize each training triplet. This means the heterogeneity issue is resolved, and you now have chain of thoughts reasoning data that you can train on, or am I misunderstanding something?

Follow-up to Question 1: The key difference between DM OPE and IPS OPE lies in how we handle the distribution mismatch. DM OPE ignores this mismatch and estimates the reward using the exploration policy, while IPS OPE addresses the mismatch and uses the ground truth reward derived from the exploration policy.

In the context of your problem, what is the distinction between the ground truth reward from the exploration policy and the possibly estimating reward? Currently, the reward function is \log \pi_0, which means that, in this case, both the ground truth and the estimate reward are the same with respect to DM and IPS, or am I misunderstanding? If this is the case, having an ablation where you remove the importance ratio \lambda term is important for me to understand where the performance benefits are coming from.

Clarification Question 1: Are you initializing the policy with SFT or the Base model when implementing your OCEAN framework?

Thank you for your quick response. I apologize for the additional questions; I want to make sure I understand what is going on.

Clarification Question 1: The only conceptual difference between the "DM OPS" baseline and the proposed KG-IPS OPE is the \lambda term being removed from handling the distribution mismatch. Does this mean that gradients with respect to both the "DM OPS" baseline and proposed KG-IPS are the same, right? So both policies should perform exactly the same with respect to all downstream tasks except for the value function estimation. The value function estimation should be different because they are different OPEs.

Clarification Question 2: The results you are showing above for "SFT w/ Verbalized KG" are w/o ctx, but I am curious about the performance improvement of SFT w/ ctx because you trained SFT w/ ctx.

Clarification Question 3: I am a bit confused regarding the statement that commonsense reasoning tasks do not require CoT. I am not very familiar with the commonsense reasoning literature, but the original CoT paper showed that CSQA performance improved with CoT [a]. Additionally, a recent Anthropic paper demonstrated that CoT helps with OpenBookQA [b].

[a] Chain-of-Thought Prompting Elicits Reasoning in Large Language Models by Wei et al.

[b] Measuring Faithfulness in Chain-of-Thought Reasoning by Chen et al.

Thank you for your valuable feedback and the time you have spent reviewing our work. We address the concerns raised and provide answers to your questions accordingly.

Response to Weakness 1

In our knowledge graph preference policy, we randomly sample reasoning trajectories to avoid potential bias on specific reasoning paths. However, in practice, exhausting every potential reasoning path is unrealistic and impractical. Thus, by leveraging the inverse propensity score (IPS), we adjust for selection bias by weighting observed data inversely proportional to the probability of selection [a,b,c]. Theoretically, we demonstrate that the IPS estimator provides an unbiased estimate of the target policy by proving that the expected value of the IPS estimator equals the true expected reward under $\pi_\theta$.

Response to Weakness 2

Several prior works [d,e,f,g] have effectively utilized knowledge graphs to align LLM reasoning with more faithful multi-hop reasoning, underscoring the validity and effectiveness of our approach to evaluating and optimizing LLMs through knowledge graph-based methods. While we do not claim that Wikidata5M encompasses all possible reasoning paths, we selected it due to its recognized comprehensiveness [j,k,l]. This choice allowed us to demonstrate the robustness and adaptability of our method. In general, our approach is adaptable and can be applied to any popular knowledge graph. Empirically, the evaluated tasks in Sections 5.2, 5.3, and 5.4 are not associated with Wikidata5M, further emphasizing the generality and versatility of our approach. By enhancing the faithfulness of reasoning, OCEAN contributes to improving LLMs’ general reasoning abilities across diverse tasks.

Response to Weakness 3

We would like to emphasize that our contributions are the offline evaluation framework to directly measure the quality of LLM chain-of-thought generation, a direct policy optimization method, and theoretical analysis of the proposed estimator. OCEAN achieves better multi-step reasoning alignment based on policy evaluation $\hat{V}(\theta)$, which demonstrates the effectiveness of improving on the CoT generation quality. We show that OCEAN consistently improves $\hat{V}(\theta)$ on multi-step reasoning generation in multi-hop question-answering tasks (in Table 1), and achieves improvements or comparable performance on knowledge-intensive tasks relying on multi-step reasoning (in Table 2).

In addition, we also show comparative results on the question-answering accuracy in multiple tasks (in Table 1, Table 2, and Table 3). However, since OCEAN does not directly learn on any supervised labels regarding question-answering tasks, the performance improvements only come from the offline policy evaluation and optimization method. Even without supervised learning on question-answering tasks, OCEAN achieves the best performance on HotpotQA and Strategy QA w/o ctx, while maintaining comparable performance on MuSiQue for multi-hop reasoning tasks (Table 1). We also observe that the best-performed LLMs on ARC, PubMedQA w/o ctx, and SciQA, are optimized by OCEAN (Table 2). In commonsense reasoning tasks, OCEAN-optimized Gemma-2 and Mistral-0.2 achieve better average performance too (Table 3).

Response to Question 1

We chose to verbalize knowledge graph trajectories instead of reformatting LLM reasoning chains as trajectories due to the inherent heterogeneity between LLM reasoning forms and structured knowledge graphs. As highlighted in Line 54 - 65 of [h], accurate grounding of reasoning chains on specific knowledge graphs is restrictive and prone to errors. Thus, directly reformatting the LLM reasoning chain as a trajectory using entity and relationship linking can be hard to adequately capture the complexity of LLM-generated thought processes and introduces bias in feedback [i]. By treating knowledge graphs as weak yet controllable reasoners, our approach aligns multi-step reasoning with multi-hop trajectories through inverse propensity scores (IPS). This ensures a more robust evaluation, leveraging the controllable structure of knowledge graphs without rigidly relying on exact reformulation or grounding.

[a] Dudík, Miroslav, John Langford, and Lihong Li. "Doubly robust policy evaluation and learning." arXiv preprint arXiv:1103.4601 (2011).

[b] Thorsten Joachims, Adith Swaminathan, and Tobias Schnabel. Unbiased learning-to-rank with biased feedback. In Proceedings of the tenth ACM international conference on web search and data mining, pp. 781–789, 2017.

[c] Edward L Ionides. Truncated importance sampling. Journal of Computational and Graphical Statistics, 17(2):295–311, 2008.

[d] Wu, Yike, et al. "CoTKR: Chain-of-Thought Enhanced Knowledge Rewriting for Complex Knowledge Graph Question Answering." Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. 2024.

[e] Sun, Jiashuo, et al. "Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph." The Twelfth International Conference on Learning Representations.

[f] Zhang, Yu, et al. "Question-guided Knowledge Graph Re-scoring and Injection for Knowledge Graph Question Answering." Findings of the Association for Computational Linguistics: EMNLP 2024. 2024.

[g] Fu, Peng, et al. "Revisiting the Knowledge Injection Frameworks." Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. 2023.

[h] Nguyen, Minh-Vuong, et al. "Direct Evaluation of Chain-of-Thought in Multi-hop Reasoning with Knowledge Graphs." arXiv preprint arXiv:2402.11199 (2024).

[i] Dudík, Miroslav, John Langford, and Lihong Li. "Doubly robust policy evaluation and learning." arXiv preprint arXiv:1103.4601 (2011).

[j] Wang, Xiaozhi, et al. "KEPLER: A unified model for knowledge embedding and pre-trained language representation." Transactions of the Association for Computational Linguistics 9 (2021): 176-194.

[k] Wang, Liang, et al. "SimKGC: Simple Contrastive Knowledge Graph Completion with Pre-trained Language Models." Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2022.

[l] Qiao, Zile, et al. "Improving Knowledge Graph Completion with Generative Hard Negative Mining." Findings of the Association for Computational Linguistics: ACL 2023. 2023.

Response to Question 5

Instead of previous works on knowledge editing or injection of LLMs that cater to specific downstream tasks, OCEAN is designed to enhance LLMs' faithfulness when generating chain-of-thought reasoning paths based on a given context.

To achieve this, we developed KG-IPS, a method for offline evaluation and optimization that measures the alignment between the likelihood of LLM-generated reasoning and a knowledge graph. Thus, OCEAN does not rely on ground truth labels (Lines 317–320) or enforce alignment to any domain-specific knowledge.

In addition, the evaluated tasks in Sections 5.2, 5.3, and 5.4 are not associated with Wikidata5M, underscoring the generality of our approach. By enhancing the faithfulness of reasoning, OCEAN contributes to improving LLMs’ general reasoning abilities across diverse tasks.

Response to Question 6

In the KG-IPS estimator, sub-Gaussian is commonly used to calculate the lower bound of the variance [o,p,q,r]. Compared to other measures, such as asymptotic normal approximations or looser Markov inequalities, sub-Gaussian bounds are non-asymptotic and offer sharper confidence intervals in finite-sample settings. These properties are especially useful in offline reinforcement learning scenarios where the number of samples is limited and fixed, and large discrepancies between policies can lead to high variance. Sub-Gaussian inequalities help keep the estimator reliable and stable in such situations.

[a]. Zhang, Zongmeng, et al. "Trustworthy Alignment of Retrieval-Augmented Large Language Models via Reinforcement Learning." arXiv preprint arXiv:2410.16843 (2024).

[b]. Gholamian, Sina, and Domingo Huh. "Reinforcement Learning Problem Solving with Large Language Models." arXiv preprint arXiv:2404.18638 (2024).

[c]. Hu, Bin, et al. "Enabling intelligent interactions between an agent and an LLM: A reinforcement learning approach." arXiv preprint arXiv:2306.03604 (2023).

[d] Yang, Mengjiao Sherry, et al. "Chain of thought imitation with procedure cloning." Advances in Neural Information Processing Systems 35 (2022): 36366-36381.

[e] Jiao, Fangkai, et al. "Learning planning-based reasoning by trajectories collection and process reward synthesizing." arXiv preprint arXiv:2402.00658 (2024).

[f] Wang, Chaojie, et al. "Q*: Improving multi-step reasoning for llms with deliberative planning." arXiv preprint arXiv:2406.14283 (2024).

[g] Li, Mo, et al. "NeedleBench: Can LLMs Do Retrieval and Reasoning in 1 Million Context Window?." arXiv preprint arXiv:2407.11963 (2024).

[h] Murthy, Rithesh, et al. "MobileAIBench: Benchmarking LLMs and LMMs for On-Device Use Cases." arXiv preprint arXiv:2406.10290 (2024).

[i] Pramanick, Shraman, Rama Chellappa, and Subhashini Venugopalan. "SPIQA: A Dataset for Multimodal Question Answering on Scientific Papers." The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track.

[j] Lou, Renze, Kai Zhang, and Wenpeng Yin. "Large Language Model Instruction Following: A Survey of Progresses and Challenges." Computational Linguistics (2024): 1-10.

[k] Chung, Hyung Won, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li et al. "Scaling instruction-finetuned language models." Journal of Machine Learning Research 25, no. 70 (2024): 1-53.

[l] Lee, Nayeon, et al. "Factuality enhanced language models for open-ended text generation." Advances in Neural Information Processing Systems 35 (2022): 34586-34599.

[m] Guan, Jian, et al. "Language Models Hallucinate, but May Excel at Fact Verification." NAACL. 2024.

[n] Tian, Katherine, et al. "Fine-Tuning Language Models for Factuality." The Twelfth International Conference on Learning Representations.

[o]. Strehl, Alex, et al. "Learning from logged implicit exploration data." Advances in neural information processing systems 23 (2010).

[p]. Alizadeh, Shima, et al. "Pessimistic off-policy multi-objective optimization." International Conference on Artificial Intelligence and Statistics. PMLR, 2024.

[q]. Agarwal, Rishabh, Dale Schuurmans, and Mohammad Norouzi. "An optimistic perspective on offline reinforcement learning." International conference on machine learning. PMLR, 2020.

[r]. Ma, Jiaqi, et al. "Off-policy learning in two-stage recommender systems." Proceedings of The Web Conference 2020. 2020.

[s] Chepurova, Alla, et al. "Better Together: Enhancing Generative Knowledge Graph Completion with Language Models and Neighborhood Information." The 2023 Conference on Empirical Methods in Natural Language Processing.

[t] Yu, Donghan, and Yiming Yang. "Retrieval-enhanced generative model for large-scale knowledge graph completion." SIGIR, 2023.

[u] Liu, Ben, et al. "UniLP: Unified Topology-aware Generative Framework for Link Prediction in Knowledge Graph." Proceedings of the ACM on Web Conference 2024. 2024.

Thank you for your valuable feedback and the time you have spent reviewing our work. We address the concerns raised and provide answers to your questions accordingly.

Response to Weakness 1

In reinforcement learning, it is common to model LLMs as MDPs [a,b,c], especially for chain-of-thought reasoning [d,e,f]. In our framework, the MDP formulation is only used to define the task and does not impact the KG-IPS estimator, which is the core component for evaluating the chain-of-thought generation process. The verbalized KG policy, as part of the IPS estimator, serves as the behavior policy to align outputs with knowledge graph preferences.

While direct on-policy optimization could theoretically be used, it is practically challenging due to the engineering effort required for step-by-step interactions with structured knowledge graphs. Our offline evaluation and optimization approach provides a simpler and more practical solution, reducing complexity while ensuring alignment with knowledge graph preferences.

Response to Weakness 2 and Question 2

Our method is not restricted to fact-based problems, as knowledge graphs often encompass abstract or conceptual knowledge. For instance, in Wikidata5M, which we use in our experiments, examples of trajectories involving abstract or conceptual knowledge include: (groups and organizations, subsystem, subclass of), (Taxonomy, Classification scheme, is a type of). In these trajectories, the third element in the tuple represents the relationship between the first two elements. By leveraging such trajectories, our method extends beyond fact-based knowledge. In addition, we evaluated OCEAN on commonsense question-answering tasks in Section 5.4, where we assessed its general reasoning ability.

Response to Weakness 3

We conducted experiments using Gemma-2 (2.8B), Phi-3.5-mini (3.8B), Llama-3 (8B), and Mistral-0.2 (7B), where multiple sizes of LLMs are assessed and they are widely used in previous works [g,h,i]. Besides, in our experiments, we found that smaller models, such as Gemma-2 and Phi-3.5-mini, exhibit limited ability to follow instructions effectively compared to larger models like Llama-3 and Mistral-0.2 [j,k]. Consequently, for even smaller LLMs, where instruction-following capabilities are inadequate, investigating issues related to factuality would lack practical relevance [l,m,n].

Response to Question 1

The primary challenge in balancing entity and non-entity token weights in the KG-IPS estimator lies in controlling the variance caused by large behavior discrepancies between the policies $\mu_\phi$ and $\pi_\theta$. The estimator avoids excessive variance accumulation by introducing separate weights for different tokens. From a theoretical perspective, the KG-IPS estimator is unbiased, ensuring accurate evaluation of the target policy $\pi_\theta$. Lemma 2 also shows that the estimator’s variance is bounded by $M^2/n$. This bound, combined with the confidence intervals $O(M \sqrt{\log(1 / \delta) / n})$, ensures robustness and stability, making the estimator reliable across different reasoning tasks.

Response to Question 3

Components such as the MDP modeling and the KG-IPS estimator are employed solely to facilitate the fine-tuning process and are not incorporated into the model as additional components. Since OCEAN is designed for offline policy evaluation and optimization, the KG-IPS estimator is only trained offline based on the reference model and used for LLMs' offline alignment. During the inference time, there is no computational overhead of OCEAN compared to the baseline CoT methods, as both approaches are prompted with the same prompt and require the same amount of computational resources. Consequently, our method does not introduce any extra parameters or computational demands, as it focuses exclusively on implementing a fine-tuning mechanism without altering the original model architecture.

Response to Question 4

Since we leverage verbalized knowledge graph trajectories as offline logged data for policy evaluation and optimization, OCEAN does not rely on any specific graph structures or domain knowledge, which is explained in Line 60 - 65. We choose Wikidata5M as an instantiation by following [s,t,u]