Knowledge Editing for Multi-Hop Question Answering Using Semantic Analysis

1 Introduction

Large Language Models (LLM) are trained on extensive amounts of data, enabling them to grasp the statistical patterns of natural language and broad factual knowledge [Brown et al., 2020]. The factual knowledge is utilized when LLMs are integrated into applications such as chatbots, translators, and question-answering systems [Zhu et al., 2024]. It is unavoidable that the factual knowledge stored within LLMs becomes outdated over time. Retraining the LLMs from scratch to learn new factual data is both economically expensive [Li et al., 2023] and introduces an undue burden on the environment [Faiz et al., 2024]. The concept of knowledge editing (KE) has emerged as a promising solution to bypass the need for retraining LLMs from scratch. Knowledge editing approaches commonly fall into two categories: parameter-based approaches that inject edits directly into model parameters [Meng et al., 2022;

Meng et al., 2023; Yu et al., 2023; Gupta et al., 2023; Hase et al., 2023] and memory-based methods that introduce additional parameters for edit injection [Mitchell et al., 2022; Madaan et al., 2022; Yu et al., 2024; Wang et al., 2024a]. Both of these solution strategies have demonstrated success for basic questioning answering problems [Meng et al., 2023; Mitchell et al., 2022]. However, the problem becomes immensely more challenging when the questions involve compositional reasoning, such as multi-hop question answering (MQA), where the intermediate knowledge between a hop could have been edited. For example, What is the country of citizenship of the author of Harry Potter, where an edit could have changed the country of citizenship of JK Rowling from United Kingdom to United States. This emerging challenge has recently spurred further investigations into knowledge editing for MQA problems [Chen et al., 2024; Shi et al., 2024].

State-of-the-art knowledge editors for MQA rely on decomposing the multi-hop problems into multiple single-hop parts [Zhong et al., 2023; Gu et al., 2024; Wang et al., 2024b]. The decomposition allows the knowledge editors to compare the intermediate facts with edits stored in a memory bank. The decomposition is performed using an LLM through long in-context examples. However, this approach is prone to leveraging illogical reasoning processes and accidentally utilizing non-relevant edited facts. An intuitive approach to improving existing solutions would be to leverage explicit question decomposition. Nevertheless, explicitly decomposing multi-hop questions into single-hop questions is not straightforward because it may introduce errors from the loss of context, nuances, and hallucinations.

In this paper, we propose a framework for knowledge editing based on semantic analysis called CHECK. The framework is based on insights from an analogy between compilers and reasoning using LLMs. Source code is first required to pass semantic analysis tests such as type checking before being compiled into a binary that can be executed. Inspired by this approach, we propose to semantically type check the reasoning chains generated by LLMs for solving MQA problems. The main contributions of this paper are summarized, as follows:

• We propose the concept of semantically analyzing the reasoning process of knowledge editors. Each hop in a multi-hop question is assigned a type in the form of per-

son, place, or thing. Next, each of the input and output types within each hop of a reasoning chain are checked for consistency.

• Semantic inconsistencies are resolved by formulating optimization problems to repair the reasoning chains by rearranging the extracted relationships or re-prompting the LLM for a new reasoning chain at a higher temperature.
• Experimental evaluation on the MQuAKE dataset demonstrates that CHECK achieves an average 22.8% greater accuracy than other similar approaches across three open-source LLMs.

The remainder of the paper is broken into the following sections: preliminary knowledge is discussed in Section 2, the motivation behind using type checking is given in Section 3, the methodology of the CHECK framework is explained in Section 4, experimental results across 4 datasets and 3 LLMs are provided in Section 5, and the conclusion is in Section 6.

2 Preliminaries

The problem formulation of knowledge editing is provided in Section 2.1. Related works are discussed in Section 2.2.

2.1 ProblemFormulation

This paper addresses the problem of Multi-hop Question Answering (MQA) under Knowledge Editing. A single factual association can be viewed as a subject s, relation r, object o triple t = (s, r, o), where Akira Toriyama was born in Japan can be converted to (Akira Toriyama, born in, Japan). Editing a factual relation is updating o to become a new entity o′ so that the edited triple becomes t′ = (s, r, o′ ). A factual association can be expressed in the form of a question q = (s, r) → o, where o is unknown until the question is answered. Multi-hop questions Q contain a chain of relations Q = (r0, r1, ..., rn) that can be viewed as a set of subquestions ((s, r0) → o1, (o1, r1) → o2, ..., (on-1, rn-1) → on) that must be iteratively solved to uncover the obscured entities until the final answer is found. For example, the multihop question Where is the birthplace of the creator of Dragonball? contains the relations (creator, birthplace), which translate into the subquestions ((Dragonball, creator) → Toriyama, (Toriyama, birthplace) → Japan). Answering any of the subquestions q of a multi-hop question Q with edited information t′ will cause the subsequent subquestion answers o′n to deviate from the original answer path, such that Q = ((s, r0) → o′1 , (o′1 , r1) → o′2 )). Generating a correct subquestion path to traverse and determining whether a subquestion requires an edited answer are the two main challenges of MQA under KE.

2.2 RelatedWorks

In this section, we review studies on knowledge editing for LLMs. Early investigation on KE using parameter-based approaches include [Meng et al., 2022; Mitchell et al., 2022; Meng et al., 2023]. However, solution strategies that directly modify model parameters face issues such as catastrophic forgetting [Gupta et al., 2024], one-way associations [Meng et al., 2022; Meng et al., 2023], and long training times [Yu et al., 2024]. Other investigations have focused on augmenting the LLM with external knowledge graphs [Cheng et al., 2024; Shi et al., 2024; Chen et al., 2024]. However, such solutions are constrained to applications where such graphs are available [Baldazzi et al., 2023]. Embedding-based editors store edits in an embedding space for compact retrieval [Zhong et al., 2023; Gu et al., 2024]. MeLLo [Zhong et al., 2023] uses the dense retrieval model Contriever [Izacard et al., 2021] to store factual edit sentences in an embedding space. Next, an in-context learning prompt is used to break the initial question into subquestions and check the subquestion answer against the most similar embedded answer for factual conflicts. PokeMQA [Gu et al., 2024] uses a similar prompting scheme, but it removes the burden of determining conflict from the LLM and trains a two-level conflict disambiguation network to determine whether the subquestion answer and retrieved embedding contain conflicting information.

The knowledge editing steps included by state-of-the-art frameworks are shown in Table 1. Neither the above knowledge editors nor similar ones have any way to ensure that the generated subquestions are being answered in an order reflecting the original multi-hop question. This results in misordered chains of subquestions, leading to a question-answering flow that will never arrive at the correct answer. The proposed CHECK framework resolves this issue by type checking the subquestion reasoning process using semantic analysis.

3 Semantic Analysis

Our proposed knowledge editing solution is based on insights from an analogy between compilers and reasoning using LLMs. Source code is converted into a binary executable through a compilation process consisting of preprocessing, semantic parsing, assembly conversion, and linking. Next, the binary can be executed to compute an output. Semantic parsing involves type checking to ensure each function call has arguments that match the function definitions. For example, checking that a function expecting an argument of type double is not passed an argument of type char. The compilation process eliminates syntactic and semantic errors, which reduces debugging of the executable to value errors. We propose to adapt this method of semantic analysis to knowledge editing for MQA by type checking the reasoning chains and knowledge edits. The type checking will ensure that the reasoning processes are logical and will assist in eliminating hallucinations from LLM responses.

In this paper, we propose to categorize all entities as persons, places, or things. Optionally, more fine-grained type categories can be used. Consequently, relationships can be viewed as functions that expect inputs and outputs of persons, places, or things. In the sentence Akira Toriyama was born in Japan, the relationship born in expects an entity of type person (Toriyama) as input and place (Japan) as output. We propose to decompose multi-hop questions into singlehop questions and iteratively resolve each relationship. If the question is decomposed correctly, the output types of one relationship are expected to overlap the input types of the next relationship. If there is no overlap between the input and output of neighboring relationships, then the semantic analysis has revealed an error that is required to be corrected before the relationship chain is evaluated to answer the MQA.

4 Methodology

In this section, we present the methodology of the CHECK framework. The input to the CHECK framework is a multihop question and a set of factual edits. The output is an answer to the questions. The CHECK framework consists of a type extraction step, a multi-hop question decomposition step, and a subquestion resolution step. The flow of the framework is illustrated in Figure 1. The type extraction step involves developing functions and a library for extracting the type of entities and relationships, respectively. The details of the type extraction is provided in Section 4.1. The multi-hop question decomposition step involves decomposing the multihop question into a chain of relationships that represent each hop and the initial multi-hop question entity. The relationship chain is then checked for type alignment and realigned if necessary. The details of question decomposition are explained in Section 4.2. The final step is to iteratively traverse the relationship chain until the answer entity is found in the subquestion resolution step. Within each iteration, the entity and relationship are compared against edits to determine whether it is necessary to insert edited information. The details of the relationship chain traversal are provided in Section 4.3.

4.1 Type Extraction

In this section, we describe how the types for both entities and relationships are extracted. The entity types are extracted using a combination of entity linking models and LLMs during MQA. In contrast, we pre-characterize a library of input and output types for the relationships. During MQA, the library is queried to obtain the input and output type of each relationship. The approach to generating types for entities and relationships is different because the number of different entities is very large and cannot be enumerated ahead of time. On the other hand, there is only a limited number of relationship that connect persons, places, and things. Therefore, it is possible to pre-characterize the different types of relationships into a template library, for quick and reliable access at runtime.

Entity Type Extraction: The objective of entity type extraction is to determine if an entity is of type person, place, or thing. We first pass the entity to an entity linking model, which can accurately decide whether the entity is a person or not. CHECK uses the ReFinED [Ayoola et al., 2022] entity linking model for its short inference times and accurate entity linking. If the entity is not a person, then the entity is passed to the language model F to determine whether the entity is a place or thing. The prompt and in-context examples are provided in Section 7 of the Appendix.

Relationship Type Extraction: The relationships from given edits are extracted to build a relationship template library, where template relationships rt are encoded using a dense retrieval model and act as keys to access their input and output types. During MQA, the template relationships rt are compared against embedded multi-hop question relationships r using cosine similarity. Question relationships r take on the input and output types of the most similar rt. Edits are expected to be provided as triples, so rt can be taken directly from the edits. Relationships can have multiple input and output types, but LLMs struggle to correctly assign multiple types at once. To generate an accurate template library, the relationship types are manually labeled, which is feasible due to the limited number of relationships.

4.2 Question Decomposition

In this section, we explain how a relationship chain is extracted from a multi-hop question. CHECK receives the multi-hop question and extracts a chain of hops that will be traversed to find the answer to the multi-hop question. Then, the input and output entity types of each relationship in the chain are checked to ensure the types are aligned. If the chain is misaligned, it is reconstructed to create a new relationship chain that is aligned.

Chain Extraction: The multi-hop question Q is passed to the LLM F along with an in-context learning prompt found, in Section 7 of the Appendix, in order to extract the relationship chain R. Relationship chain extraction is outlined as follows:

where R is a chain of relationships (r0, r1, ..., rn). The initial entity on from Q is extracted using an entity linking model. The relationship chain R can be iteratively traversed backwards to generate triples (on, rn, on-1) until on-1 is the final answer o0 to Q. The traversal process can be viewed as a series of function calls where rn is a function that takes on as input and outputs on-1 such that o0 = r1(r2(rn(on))). Relationship chain traversal is described in-depth in Section 4.3.

Chain Alignment: The extracted relationship chains R have been observed to contain misaligned relationships r. Misalignment occurs when the ordering of r within R does not match the ordering of relationships within the original multi-hop question. To check the alignment of the extracted chain, all r in R are given input Tin and output Tout types, as described in Section 4.1. The relationships types are combined to form a chain C of types corresponding to R, such that:

The alignment penalty A for a type chain C is determined by the number of input and output type pairs n that are misaligned. The alignment of C is described as follows:

where a misalignment T out i ̸= T in i+1 carries a penalty of 1, while an alignment T out i == T in i+1 carries no penalty. The penalty values mi are summed to get A. If A == 0, C is properly aligned and is passed to the subquestion resolution step. If A > 0, CHECK attempts to find an aligned C.

Relationship Chain Repair: When a relationship chain R is not aligned, we have observed that R often contains the correct relationships, only in an incorrect order. Therefore, there exists an opportunity to correct the misaligned chains by permuting the relationships to find an aligned chain. The relationship chain repair step starts by generating all permutations of the relationship type chain C. The repair is successful if one of the permutations c has an alignment penalty of zero A(c) = 0. However, there may be multiple permuted chains that have an alignment penalty of zero. If multiple c exist where A(c) = 0, we select c that has the smallest permutation cost λ, the c that required the smallest number of permutations to eliminate the alignment penalty.

To find λ for each c, the permutation matrix P used to generate c is examined. Generating c using P can be described as P · R = c, and expanded as:

where Cn and cn correspond to the input / output type pairs within the the original type chain C and its permutations c.

The rows in P can be reordered to obtain a different permutation c, as long as each row and column has exactly 1 non-zero value. CHECK attempts to find a c where A(c) = 0 and the permutation penalty λ of P is minimal. The penalty λ of the permutation matrix P is computed as follows:

where Pr,c denotes the element in row r and column c of P. The summation computes the number of elements that are on the diagonal, which corresponds to the number of elements in their "unpermuted" position. Subtracting the sum from the number of diagonal elements N provides the number of rows that have been permuted, also known as the permutation cost λ for the current permutation c. The initial permutation matrix P will have the value 1 on all diagonal matrix elements Pi,i, so the λ for C will be 0, while λ for any permutation c will be non-zero.

Equation 3 is applied to all generated c. If at least 1 permutation c where A(c) = 0 exists, the c where A(c) = 0 with the lowest λ is used as the new C and the corresponding permutation of R is passed to the subquestion resolution step.

If an aligned c does not exist, then question decomposition is restarted and a higher LLM temperature is used during chain extraction. We use a temperature scale of 0.0 to 1.0 on increments of 0.1. After 1.0, the model responses tend to become too varied to be useful. The 0.1 increment gives a good trade-off between exploring many options and while still having a reasonable run time. If no aligned c is found, the c with the least A is used during subquestion resolution.

4.3 Subquestion Resolution

The input to the subquestion resolution step is an entity on and relationship r. The goal is to generate the next entity on-1. Starting with the initial entity and relationship, the current on and r are compared against stored edits. If an edit that is sufficiently similar to one of the inputs exists, the next entity on-1 will be an edited object o′ from the corresponding edit triple t′ . Otherwise, the LLM is prompted to generate and answer a question based on the current on and r to find on-1.

This process is repeated until the final multi-hop answer has been obtained. Each entity and relationship is embedded using a dense retrieval model and is compared against all edit embeddings using cosine similarity. An example of subquestion resolution is provided in Figure 3.

Edit Storage: Prior to MQA, CHECK receives edits as triples and stores them as strings and embeddings. Edit triples t′ are stored as comma-separated lists. The subject s of t′ is passed to an entity linking model to get the true name s∗ of the entity. The edit triple t′ is then updated with s∗ such that t′ = (s∗ , r, o′ ).

Edits t′ are also stored in an embedding space. The subject s and relationship r of t′ are combined into one string and passed to an embedding model to get an edit embedding. Following previous works, we use the Contriever [Izacard et al., 2021] dense retrieval model. These embeddings are then used during relationship chain traversal to aid in determining whether an edit needs to be made.

Edit Retrieval: The initial entity on is passed to an entity linking model to generate its true name o∗n . The initial entity true name o∗n is compared against all true edit names s∗ previously inserted into CHECK. Next, the list of edit triples Lt is searched for corresponding edits as follows:

where the set of semantic embeddings that will be checked for necessary edits Esearch is narrowed to the embeddings Es∗ where s∗ ∈ L and o∗n == s∗ . The entity linking model can generate false positive and false negative outputs, so even if no match is found, all edited semantic embeddings εe ∈ E are checked to ensure that an edit is not missed.

Once Esearch has been found, the initial entity on and relationship rn of Q are extracted from R and passed to a dense retrieval model to generate semantic embeddings εc for the current hop. Then, εe ∈ E are compared against εc using cosine similarity cos(). If the highest similarity embedding is above a threshold τ, then the o′ from the corresponding edit triple t′ becomes the new on-1. If the highest similarity is below τ , then on and rn move to the triple completion sub-step. Semantic embedding matching can be described algorithmically as follows:

If no new on-1 is found through semantic embedding similarity, then the LLMF is prompted to generate the next on-1. First, F is prompted using in-context learning to generate a question QLLM based on on and rn. The question-generating in-context learning prompt is provided in Section 7 of the Appendix. The LLM-generated question QLLM is then answered by F using another in-context learning prompt to ensure that only a single entity on-1 is provided as an answer.

Once on-1 is generated through one of the previous substeps, it is paired with rn-1 to complete the previous two sub-steps to find on-2. This process is iteratively completed [(on, rn, on-1) → (on-1, rn-1, on-2) → ... → (o1, r1, o0)] until all rn have been used and the final answer o0 is found.

5 Results

The code for CHECK is available at https://github.com/ dominic-simon/CHECK.

Baselines: We compare against other editors that do not rely on outside sources of factual information. Specifically, we compare against MeLLo [Zhong et al., 2023], PokeMQA [Gu et al., 2024], DeepEdit [Wang et al., 2024b], and the question-answering portion of GMeLLo [Chen et al., 2024]. We also provide comparisons against the parameterbased knowledge editors ROME [Meng et al., 2022] and MEMIT [Meng et al., 2023] as well as model finetuning.

Datasets: We use the MQuAKE [Zhong et al., 2023] dataset to evaluate the editors. MQuAKE is composed of two subsets. The counterfactual subset contains 3000 edit cases. The subset contains questions with 2, 3, and 4 hops with 1000 cases of each. Each edit case contains betwen 1 and 4 individual edits. The temporal subset is composed of 1868 edit cases containing 1421 2-hop questions, 445 3-hop questions, and 2 4-hop questions each with only 1 edit. Two additional subsets have also been added to MQuAKE [Wang et al., 2024b]. The counterfactual subset contains conflicting edit cases, so MQuAKE-2002 removes all cases with conflicting edits, resulting in a counterfactual dataset containing only 2002 edit cases. The other new subset contains 429 edit cases each with 4 hops and 4 edits.

Evaluation Metrics: Each edit case in MQuAKE contains 3 multi-hop questions conveying the same idea with the same number of hops in slightly different words. An edit case is considered correct if the editor correctly answers at least 1 question. We also track the number of questions each editor has answered correctly. Per-case accuracy is determined as correct cases ÷ total cases and per-question accuracy is determined as correct questions ÷ total questions.

Models: We compare the baselines across 3 models: GPTJ [Wang and Komatsuzaki, 2021], Vicuna-7B [Chiang et al., 2023], and Falcon-7B [Almazrouei et al., 2023].

Implementation: MeLLo and PokeMQA were limited to 5 hops to keep the experiment time reasonable. Similarly, DeepEdit was allowed 5 additional knowledge candidates. Additionally, they were each allowed a maximum of 200 new tokens to be generated for each LLM call. CHECK used a cosine similarity threshold of 0.8 and was limited to a maximum of 50 new tokens per model call.

Hardware Setup: All experiments were conducted on 1 NVIDIA A100 GPU and 8 CPU cores.

We present two core experiments in the following sections: an evaluation of CHECK against other knowledge editors across 4 datasets and 3 LLMs in Section 5.1, and an ablation study on the performance of CHECK over varying numbers of hops and edits in Section 5.2. Additional experiments are provided in the Appendix.

5.1 Editing Accuracy

The evaluation of CHECK and other state-of-the-art multihop knowledge editors is provided in Table 2. Across all models, GMeLLo, MeLLo, DeepEdit, and PokeMQA consistently struggle to achieve a 20% per-case accuracy on three of the four subsets. The only subset they are able to find better performance on is MQuAKE-T, which contains the least number of hops and edits per question. This is unsurprising as they all rely on LLMs doing large amounts of reasoning at once. DeepEdit is able to break the 20% per-case accuracy mark in a few of the results and PokeMQA overpeforms on Vicuna when compared to its performance on GPT-J and Falcon. CHECK does not share this struggle of breaking 20% per-case accuracy, achieving a 31.57%, 28.51%, 24.79%, and 16.77% increase in accuracy over the next highest on the MQuAKE-CF-3k, MQuAKE-2002, MQuAKE-Hard, and MQuAKE-T subsets respectively.

Parameter-based knowledge editors have proven unsuccessful on mutli-hop questions. An evaluation of the accuracy of CHECK and other parameter-based knowledge editors on MQuAKE subsets is provided in Table 3. The accuracies are from [Shi et al., 2024]. CHECK outperforming the parameter-based editors is in line with previous works, further affirming that storage-based knowledge editors are better able to handle the intermediate reasoning steps required for MQA than parameter-based knowledge editors.

5.2 MQAHop and Edit Ablation

We provide a breakdown of CHECK's per-case accuracy on MQuAKE-3k and MQuAKE-2002 over the number of hops and edits in Figure 4 and Figure 5, respectively. As the the number of hops increases, the accuracy of CHECK decreases. This is an expected outcome since longer multi-hop questions require longer relationship chains, introducing more areas for both question decomposition and subquestion resolution to fail. Similarly, as the number of edits increases, the accuracy also drops. Greater number of edits correspond to longer questions, which are more difficult to correctly answer. CHECK's over-performance on questions with 2 edits can be attributed to the in-context learning prompt used during question decomposition.

6 Conclusion

We present the CHECK framework for multi-hop knowledge editing. The main insight of CHECK is that the LLM subquestion reasoning process can be checked for semantic consistency. CHECK decomposes multi-hop questions into a chain of relationships and ensures the semantic consistency of that chain. The chain is then iteratively traversed, answering each of the subquestions that make up the chain and inserting edits where necessary until the answer to the multi-hop question is reached.

Acknowledgements

This material is in part sponsored by UF startup funds and DARPA under agreement number FA8750-23-2-0501. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of DARPA or the U.S. Government.