KnowTrace: Explicit Knowledge Tracing for Structured Retrieval-Augmented Generation

We sincerely appreciate your careful reading and positive comments on our paper. Below, we provide a detailed response to your concerns and questions.

Q1: Include a cost analysis of KnowTrace.

Thanks for raising this important point. We follow your suggestion to include a detailed cost and latency analysis for our KnowTrace and two representative baselines (i.e., IRCoT and ERA-CoT). The statistics are summarized as follows:

#Iteration: Average number of inference iterations per question
#Token: Average number of tokens processed by LLMs per question
#Time: Average inference time per question

We can observe that:

• Compared to the iterative baseline IRCoT, KnowTrace requires fewer iterations on average, since it can explore multiple expansion directions based on the current knowledge structure at each iteration, rather than solely relying on a single chain of thought. This allows KnowTrace to acquire more relevant knowledge in each iteration, reducing the overall number of iterations required.
• For the restructuring-based baseline ERA-CoT, although it is a non-iterative approach (#Iteration = 1.0), its restructuring process involves 5 LLM-driven steps (entity extraction, relation extraction, relation inference, discrimination, and question answering) for every input question. These steps are inherently non-parallelizable and all require retrieved passages to be included in the LLM prompts. Therefore, the resturcturing operations in ERA-CoT incur significantly higher inference time cost than both IRCoT and our KnowTrace.
• Overall, beyond the iterative and restructuring-based baselines, KnowTrace seamlessly integrates knowledge structuring with multi-step reasoning, enhancing inference performance without sacrificing the efficiency. In other words, KnowTrace achieves a favorable balance of computational cost and multi-step reasoning capability compared to both iterative and restructuring-based baselines.

At the same time, we would like to respectfully clarify that the backtracing mechanism naturally leverages the knowledge structures organized during KnowTrace inference without additional LLM calls. This mechanism produces high-quality rationales for self-improvement training, whose cost aligns with standard parameter-efficient fine-tuning (approximately 2–3 hours on a single NVIDIA A100 GPU).

Q2: Would KnowTrace be possible to directly retrieve from external KG?

Yes, KnowTrace is able to leverage external KG to enhance LLM inference. Specifically, after determining the entity-relation pair $(e, r)$ to explore in the current iteration, KnowTrace can naturally adopt a structured retrieval approach: first, select the top-$m$ entities from the external KG that are most similar to $e$; next, among the relations associated with these entities, select the top-$n$ relations most similar to $r$; the triplets corresponding to these entities and relations in the external KG are then traced out for this iteration.

We validate the effectiveness of this approach on a standard multi-hop KGQA dataset (CWQ [1]). The EM results are shown as follows, demonstrating that KnowTrace can effectively acquire relevant knowledge triplets from external KG to enhance LLM inference.

Q2: How to address the supporting facts that may be difficult to represent solely in the form of triplets?

Indeed, certain information, such as temporal attributes, quantities, or qualitative descriptions, may not be neatly expressed as the standard subject-predicate-object triplets in conventional knowledge graphs. To address this, KnowTrace adopts a more flexible approach by allowing free-form textual descriptions within the structured triplets. This enables the representation of nuanced relationships and attributes. For example, from "John moved to Paris before 2015", the free-form triplet could be: (John, moved to before 2015, Paris), embedding temporal attribute directly into the relation. This flexible representation allows KnowTrace to adaptively trace and structure knowledge even in cases where conventional triplet formats fall short. We believe this adaptability is key to handling the complexity of datasets like HotpotQA and MuSiQue effectively.

References:
[1] Unifying Structure Reasoning and Language Model Pre-training for Complex Reasoning
[2] Triggering Multi-Hop Reasoning for Question Answering in Language Models using Soft Prompts and Random Walks
[3] Graph-Guided Reasoning for Multi-Hop Question Answering in Large Language Models
[4] Semi-Structured Chain-of-Thought: Integrating Multiple Sources of Knowledge for Improved Language Model Reasoning
[5] Boosting Language Models Reasoning with Chain-of-Knowledge Prompting

We sincerely appreciate your careful reading and valuable comments on our paper. Below, we provide a detailed response to your concerns and questions.

Q1: Compare KnowTrace with more prior works, and highlight the unique contributions.

We understand your concern and appreciate the opportunity to clarify the novelty of our work compared to [1–5]. Below, we highlight the key distinctions and our unique contributions.

Comparison with [1] and [2]: These two works focus on constructing masked knowledge structures as training data for pretraining (or finetuning) language models, aiming to imbue the models with structural reasoning capabilities. Specifically, they construct training datasets by first restructuring Wikipedia documents and then masking specific (predefined or random-walk-generated) entities within the structures. In contrast, our method does not rely on such structural pretraining or dataset construction, but instead operates directly on unstructured text, actively tracing relevant knowledge in the form of triplets during multi-step inference.

Comparison with [3] and [4]: These two works focus on parsing input questions into masked structured chains and subsequently rely either on existing external knowledge graphs to fill missing triplets or rewrite missing triplets as natural language queries to retrieve answers from external text databases. However, such approaches heavily depend on the accuracy of the initial parsing---errors at this stage can propagate---thereby necessitating careful filtering and consistency operations [4]. In contrast, KnowTrace adopts a more flexible perspective of adaptively tracing knowledge triplets during the multi-step reasoning process, rather than solely relying on the one-time parsing of the input question. This adaptive exploration can reduce error propagation and enhance robustness.

Comparison with [5]: This work retrieves candidate triplets from a pre-constructed KG and combines them with human annotations, aiming to design effective exemplars that induce fact generation capabilities of LLMs. In contrast, our work pursues a different objective, i.e., tracing and expanding structured knowledge directly from unstructured text during multi-step reasoning process to enhance the multi-step reasoning capabilities of LLMs.

Overall, the unique contributions of our work are summarized as follows:

Flexible Knowledge Exploration and Structuring. KnowTrace actively traces knowledge triplets relevant to the input question during multi-step reasoning process. Such a perspective enables more flexible LLM inference and does not require additional structural training or one-time parsing of the input.

Transparent Reasoning Procedure. The progressive expansion of structured knowledge memory in our KnowTrace framework not only enhances LLM inference, but also provides a transparent record of the reasoning Procedure. This transparency allows for the natural backtracing mechanism to distill higher-quality rationales, which can further be leveraged for post-training (e.g., self-improvement).

Complementary to the Prior Works. The proposed framework is orthogonal to the techniques in [1–5], and one can integrate them to further enhance the reasoning capabilities of LLMs. For instance, KnowTrace could use models pre-trained with structural reasoning (as in [1], [2]) as the backbone or incorporate pre-parsed question structures (as in [3], [4]) to assist in the knowledge exploration phase.

We hope these detailed comparisons address your concern, and will incorporate these discussions into the revision for better positioning our proposal relative to the prior works [1-5].

Dear Reviewer Tjwb,

Thank you very much for your time and insightful feedback. We have addressed your questions and comments with detailed clarifications. We would greatly appreciate it if you could reconsider your rating. Additionally, we are more than happy to answer any further questions you may have.

Our responses can be outlined as follows:

• First, we provided a detailed clarification of the key distinctions between our framework and the prior works [1-5].
• Second, we highlighted the unique contributions of our work, including
  • Flexible Knowledge Exploration and Structuring
  • Transparent Reasoning Procedure for Backtracing
  • Complementary to the Prior Works
• Third, we clarified that: to enable the representation of nuanced relationships and attributes, KnowTrace allows free-form textual descriptions within the structured triplets, which we believe is crucial for handling the complexity of datasets like HotpotQA and MuSiQue effectively.

Best regards,
Authors

Thank you for your response. It addressed some of my concerns, and I will improve my score. Please consider adding this discussion to the final version.

Q4: How many numbers of iterations does KnowTrace adopted in the experimental results of Table 1?

We understand your concern about the inference overhead of our framework. To effectively address this, we include a detailed cost and latency analysis for KnowTrace and two representative baselines (i.e., IRCoT and ERA-CoT). The statistics are summarized as follows:

#Iteration: Average number of inference iterations per question
#Token: Average number of tokens processed by LLMs per question
#Time: Average inference time per question

We can observe that:

• Compared to the iterative baseline IRCoT, KnowTrace requires fewer iterations on average, since it can explore multiple expansion directions based on the current knowledge structure at each iteration, rather than solely relying on a single chain of thought. This allows KnowTrace to acquire more relevant knowledge in each iteration, reducing the overall number of iterations required.
• For the restructuring-based baseline ERA-CoT, although it is a non-iterative approach (#Iteration = 1.0), its restructuring process involves 5 LLM-driven steps (entity extraction, relation extraction, relation inference, discrimination, and question answering) for every input question. These steps are inherently non-parallelizable and all require retrieved passages to be included in the LLM prompts. Therefore, the resturcturing operations in ERA-CoT incur significantly higher inference time cost than both IRCoT and our KnowTrace.
• Overall, beyond the iterative and restructuring-based baselines, KnowTrace seamlessly integrates knowledge structuring with multi-step reasoning, enhancing inference performance without sacrificing the efficiency. In other words, KnowTrace achieves a favorable balance of computational cost and multi-step reasoning capability compared to both iterative and restructuring-based baselines.

At the same time, we would like to respectfully clarify that the backtracing mechanism naturally leverages the knowledge structures organized during KnowTrace inference without additional LLM calls. This mechanism produces high-quality rationales for self-improvement training, whose cost aligns with standard parameter-efficient fine-tuning (approximately 2–3 hours on a single NVIDIA A100 GPU).

References:
[1] Shi et al. Large Language Models Can Be Easily Distracted by Irrelevant Context. ICML 2023.
[2] Wei et al. InstructRAG: Instructing Retrieval-Augmented Generation via Self-Synthesized Rationales. 2024.

Q2: Better presentation with an actual example of KnowTrace.

Thanks for your valuable suggestion regarding the inclusion of an example to enhance the clarity of our framework. Following this suggestion, we provide a detailed example of KnowTrace inference and backtracing below, and will include it in our revision to complement the high-level presentation in Figure 1.

Example of KnowTrace Inference:

Input Question: Where was the person who wrote about the rioting being a dividing factor in Birmingham educated?

[Iteration 1]
### Knowledge Memory: None
### Knowledge Exploration
Whether the collected knowledge triplets are sufficient: No
What entity-relation pairs to retrieve in the current step: 
- The rioting being a dividing factor in Birmingham: Find out who wrote about this topic. 
- Birmingham: Find out where Birmingham is located.
### Retrieve Textual Passages From Wikipedia
### Knowledge Completion
(James Watt, wrote about, the rioting being a dividing factor in Birmingham); 
(James Watt, is, an industrialist); 
(Birmingham, is located in, the West Midlands region of England)

[Iteration 2]
### Knowledge Memory: The Knowledge Triplets Acquired in Iteration 1
### Knowledge Exploration
Whether the collected knowledge triplets are sufficient: No
What entity-relation pairs to retrieve in the current step: 
- James Watt: Find out which school James Watt attended.
### Retrieve Textual Passages From Wikipedia
### Knowledge Completion
(James Watt, was educated at, University of Glasgow)

[Iteration 3]
### Knowledge Memory: The Knowledge Triplets Acquired in Iterations 1 and 2
### Knowledge Exploration
Whether the collected knowledge triplets are sufficient: Yes
Thought: James Watt wrote about the rioting being a dividing factor in Birmingham. He was educated at the University of Glasgow.
Answer: University of Glasgow

Example of Backtracing Mechanism:
Based on the transparent knowledge structure traced by KnowTrace in the above example, we can naturally backtrace from the answer entity University of Glasgow to identify the following evidence subgraph: (James Watt, wrote about, the rioting being a dividing factor in Birmingham); (James Watt, was educated at, University of Glasgow). In this way, our framework naturally allows for filtering unavailing exploration (e.g., "- Birmingham: Find out where Birmingham is located") and extraneous completion (e.g., (James Watt, is, an industrialist)) from the LLM generations, thereby presenting higher-quality reasoning rationales for the self-improvement finetuning.

Q3: Could KnowTrace* be further enhanced with the iterative baselines or other related works such as InstructRAG [2]?

Yes, we agree with the potential to further enhance our framework via incorporating rationales or insights from the related works. For instance, the positive rationales (i.e., rationales leading to correct answers) generated by iterative RAG approaches could serve as auxiliary signals to guide KnowTrace* in producing higher-quality dataset for further finetuning.

The concurrent work InstructRAG leverages additional LLM calls to generate rationales that explain how answers are derived from retrieved passages. Our framework could also naturally integrate this idea to augment the finetuning dataset, i.e., invoking LLMs to provide more detailed explanations for the KnowTrace rationales distilled by the backtracking mechanism, thereby stimulating more effective self-improvement finetuning for KnowTrace*.

Overall, we believe that these directions offer valuable avenues for future work to further enhance our framework. We sincerely appreciate your insightful feedback.

We sincerely appreciate your careful reading and valuable comments on our paper. Below, we provide a detailed response to your concerns and questions.

Q1: Compare KnowTrace with restructuring-based RAG approaches in the iterative setting.

We would first like to respectfully clarify that although the restructuring-based RAG approaches (such as ERA-CoT) are non-iterative, they typically involve multiple intricate LLM-driven operations. For instance, the restructuring process of ERA-CoT contains 5 LLM-driven steps (entity extraction, relation extraction, relation inference, discrimination, and question answering) for every input question. These steps are inherently non-parallelizable and all require retrieved passages to be included in the LLM prompts, thereby incurring even higher inference overhead than both iterative approaches (such as IRCoT) and our KnowTrace framework (you could find a detailed cost analysis in our response to your Q4).

At the same time, we understand your concern about the performance (rather than inference overhead) comparison between iterative restructuring-based baselines and our KnowTrace. To address this, we extend ERA-CoT into the standard iterative setting for evaluation: iteratively propose new query for retrieval and restructure all retrieved passages until sufficient information is collected to derive the final answers. The EM/F1 and #Time (average inference time per question) results on HotpotQA dataset are summarized as follows:

(#Time: Average inference time per question)

We can observe that iterative ERA-CoT outperforms its one-time counterpart but significantly increases the inference time per question. In contrast, KnowTrace achieves more substantial performance gains without incurring high inference cost. We attribute this to the favorable perspective of explicit knowledge tracing in our framework, which avoids the intricate process of indiscriminately restructuring all retrieved passages. Such restructuring process used in (iterative) ERA-CoT may retain extensive irrelevant information while overlooking knowledge critical to the input question, which could negatively impact the subsequent query generation and the final answer inference [1].

We hope this comparison clarifies the unique advantages of KnowTrace over both iterative and one-time restructuring-based RAG approaches.

Dear Reviewer ifaQ,

Thank you very much for your time and insightful feedback. We have addressed your questions and comments with detailed clarifications and additional experiments. We would greatly appreciate it if you could reconsider your rating. Additionally, we are more than happy to answer any further questions you may have.

Our responses can be outlined as follows:

• First, we conducted additional experiments to compare KnowTrace with the iterative version of the restructuring-based baseline ERA-CoT, and found that our framework exhibits the dual advantages in performance and efficiency.
• Second, we followed your suggestion to include a specific example of KnowTrace inference and backtracing mechanism, which complements the high-level presentation in Figure 1.
• Third, we discussed the potential of further integrating our framework with the insights from the other related works, which offers valuable avenues for future study.
• Last but not least, we presented a detailed cost and latency analysis for our KnowTrace and two representative baselines, aiming to address your concern about the inference overhead of our framework.

Best regards,
Authors

Thank the authors for their clear responses and additional experiments! The answers address much of my original concerns, especially relative to the cost/overhead of inference process. I have raised the score accordingly.

I want to thank the authors again for their great effort in responding to my questions.

Q2: Generalizability of KnowTrace on entire test set and other open-domain QA tasks.

We would first like to respectfully clarify that our experiments adopt the same evaluation settings as prior works (e.g., IRCoT, Iter-RetGen, and SG-Prompt) for consistency.

At the same time, we totally understand your concerns regarding the generalizability of our framework. To address this, we follow your suggestion to evaluate KnowTrace (and two representative baselines) on the entire test set of three multi-hop QA datasets as well as two additional open-domain QA datasets. The EM results are summarized as follows:

We can observe that:

• On the full test sets of the three standard multi-hop QA datasets, KnowTrace maintains superior performance, thereby confirming the effectiveness and generalizability of our framework on the multi-hop QA task.
• While our work is primarily designed for the complex multi-hop QA task, KnowTrace still outperforms IRCoT and performs comparably to ERA-CoT on the two simpler open-domain QA datasets, i.e., NaturalQuestions (NQ) and TriviaQA (TQA).
• These results comprehensively confirm that our framework can effectively handle complex multi-hop questions without compromising performance on simpler ones.

Q3: How are the rationales generated given the correct trajectories in Figure 1? Does this process involve a new LLM invocation?

For the backtracing mechanism, the reasoning rationales are distilled by tracing back along the self-organized knowledge structures from the target entities to the initial entities as described in Section 3.3. In other words, this process is inherently built upon the knowledge structures acquired during KnowTrace inference, and does not require any additional LLM invocations.

To address your concern more clearly, we provide a detailed example of KnowTrace inference and backtracing below.

Example of KnowTrace Inference:

Input Question: Where was the person who wrote about the rioting being a dividing factor in Birmingham educated?

[Iteration 1]
### Knowledge Memory: None
### Knowledge Exploration
Whether the collected knowledge triplets are sufficient: No
What entity-relation pairs to retrieve in the current step: 
- The rioting being a dividing factor in Birmingham: Find out who wrote about this topic. 
- Birmingham: Find out where Birmingham is located.
### Retrieve Textual Passages From Wikipedia
### Knowledge Completion
(James Watt, wrote about, the rioting being a dividing factor in Birmingham); 
(James Watt, is, an industrialist); 
(Birmingham, is located in, the West Midlands region of England)

[Iteration 2]
### Knowledge Memory: The Knowledge Triplets Acquired in Iteration 1
### Knowledge Exploration
Whether the collected knowledge triplets are sufficient: No
What entity-relation pairs to retrieve in the current step: 
- James Watt: Find out which school James Watt attended.
### Retrieve Textual Passages From Wikipedia
### Knowledge Completion
(James Watt, was educated at, University of Glasgow)

[Iteration 3]
### Knowledge Memory: The Knowledge Triplets Acquired in Iterations 1 and 2
### Knowledge Exploration
Whether the collected knowledge triplets are sufficient: Yes
Thought: James Watt wrote about the rioting being a dividing factor in Birmingham. He was educated at the University of Glasgow.
Answer: University of Glasgow

Example of Backtracing Mechanism:
Based on the transparent knowledge structure traced by KnowTrace in the above example, we can naturally backtrace from the answer entity University of Glasgow to identify the following evidence subgraph: (James Watt, wrote about, the rioting being a dividing factor in Birmingham); (James Watt, was educated at, University of Glasgow). In this way, our framework naturally allows for filtering unavailing exploration (e.g., "- Birmingham: Find out where Birmingham is located") and extraneous completion (e.g., (James Watt, is, an industrialist)) from the LLM generations, thereby presenting higher-quality reasoning rationales for the self-improvement finetuning.

We sincerely appreciate your careful reading and valuable comments on our paper. Below, we provide a detailed response to your concerns and questions.

Q1: Inference efficiency of KnowTrace (Cost and Latency Study).

We understand your concern about the inference overhead of our framework. To effectively address this, we include a detailed cost and latency analysis for KnowTrace and two representative baselines (i.e., IRCoT and ERA-CoT). The statistics are summarized as follows:

#Iteration: Average number of inference iterations per question
#Token: Average number of tokens processed by LLMs per question
#Time: Average inference time per question

We can observe that:

• Compared to the iterative baseline IRCoT, KnowTrace requires fewer iterations on average, since it can explore multiple expansion directions based on the current knowledge structure at each iteration, rather than solely relying on a single chain of thought. This allows KnowTrace to acquire more relevant knowledge in each iteration, reducing the overall number of iterations required.
• For the restructuring-based baseline ERA-CoT, although it is a non-iterative approach (#Iteration = 1.0), its restructuring process involves 5 LLM-driven steps (entity extraction, relation extraction, relation inference, discrimination, and question answering) for every input question. These steps are inherently non-parallelizable and all require retrieved passages to be included in the LLM prompts. Therefore, the resturcturing operations in ERA-CoT incur significantly higher inference time cost than both IRCoT and our KnowTrace.
• Overall, beyond the iterative and restructuring-based baselines, KnowTrace seamlessly integrates knowledge structuring with multi-step reasoning, enhancing inference performance without sacrificing the efficiency. In other words, KnowTrace achieves a favorable balance of computational cost and multi-step reasoning capability compared to both iterative and restructuring-based baselines.

At the same time, we would like to respectfully clarify that the backtracing mechanism naturally leverages the knowledge structures organized during KnowTrace inference without additional LLM calls. This mechanism produces high-quality rationales for self-improvement training, whose cost aligns with standard parameter-efficient fine-tuning (approximately 2–3 hours on a single NVIDIA A100 GPU).