# Leveraging Logical Rules in Knowledge Editing: A Cherry on the Top

Keyuan Cheng∗,1,2,3, Muhammad Asif Ali∗,1,2, Shu Yang∗,1,2, Gang Lin1,2,3,
Yuxuan Zhai1,2,3, Haoyang Fei1,2,3, Ke Xu3, Lu Yu4, Lijie Hu†,1,2, and Di
Wang†,1,2
1Provable Responsible AI and Data Analytics (PRADA) Lab
2King Abdullah University of Science and Technology
3South China University of Technology 4Ant Group The first three authors
contributed equally to this work.Correspondence to Lijie Hu
<EMAIL_ADDRESS>and Di Wang<EMAIL_ADDRESS>
###### Abstract

Multi-hop Question Answering (MQA) under knowledge editing (KE) is a key
challenge in Large Language Models (LLMs). While best-performing solutions in
this domain use a plan and solve paradigm to split a question into sub-
questions followed by response generation, we claim that this approach is sub-
optimal as it fails for _hard to decompose_ questions, and it does not
explicitly cater to _correlated knowledge updates_ resulting as a consequence
of knowledge edits. This has a detrimental impact on the overall consistency
of the updated knowledge. To address these issues, in this paper, we propose a
novel framework named Rule-Ke, _i.e.,_ Rule based Knowledge Editing, which is
a cherry on the top for augmenting the performance of all existing MQA methods
under KE. Specifically, Rule-Ke leverages rule discovery to discover a set of
logical rules. Then, it uses these discovered rules to update knowledge about
facts highly correlated with the edit. Experimental evaluation using existing
and newly curated datasets (_i.e.,_ RKe-eval) shows that Rule-Ke helps augment
both performances of parameter-based and memory-based solutions up to 92% and
112.9%, respectively.

##  1 Introduction

Large Language Models (LLMs) have demonstrated powerful reasoning and
comprehension capabilities for worldly knowledge Huang2022TowardsRI ;
Wei2022ChainOT . However, it has been shown that LLMs have a very limited
adaptability to newly emerging information and/or knowledge jeong2023study .
This causes LLMs to generate plausible yet incorrect answers for unknown
facts, a phenomenon known as hallucinations Hong2023FaithfulQA ; 2023survey .
Moreover, such a weakness significantly undermines the reliability of LLMs for
Multi-hop Question Answering (MQA), which requires multiple reasoning steps
and extensive open-domain knowledge Lan2021ASO ; Mavi2022ASO . Updating LLMs’
information/knowledge through model re-training is a computationally demanding
tasks, making well-timed edits almost impossible. Thus, to avoid re-training,
MQA under knowledge editing (KE), _i.e.,_ answering multi-hop questions based
on given fact edits, has thus received much attention in recent years
gu2023pokemqa ; zhong2023mquake .

Briefly speaking, there are two dominant research directions for this topic,
_i.e.,_ parameter-based and memory-based knowledge editing. Parameter-based
methods update the knowledge in LLMs by modifying the parameters of the model.
Some examples in this regard include ROME meng2022locating  and its improved
variant, _i.e.,_ MEMIT meng2022mass . On the contrary, the memory-based
methods explicitly maintain an edit memory to store the information about the
knowledge and facts to be modified. Examples include: MeLLo zhong2023mquake ,
PokeMQA gu2023pokemqa  and Temple-MQAcheng2024multi . These methods primarily
adopt plan-and-solve paradigm Khot2022DecomposedPA ; Wang2023PlanandSolvePI ,
where LLMs are prompted to decompose a multi-hop question into multiple sub-
questions followed by iteratively interacting with the edit memory to solve
each sub-question.

Figure 1: (a) The former company of Tom is Amazon, after updating the Tom’s
company to Twitter the model still has past knowledge about Tom’s boss. (b)
Rule-Ke leverages logic rules to also update knowledge about Tom’s boss to
Elon Musk following the edit about Tom’s company.

While recently plenty of work has contributed to MQA under KE, we observe that
existing research still poses following key limitations: (i) These methods
will fail when encountering "_hard to decompose_ " multi-hop questions, and
(ii) they are unable to cater to "_correlated knowledge updates_ " resulting
as a consequence of knowledge edits. Here "_hard to decompose_ " questions
imply a subset of multi-hop questions that cannot be easily decomposed into
independent sub-questions using existing plan-and-solve approaches (_e.g.,_
zhong2023mquake ; gu2023pokemqa ). Likewise, "_correlated knowledge update_ "
implies cases where we need to cater to successive knowledge updates resulting
as a consequence of individual knowledge edits to come up with the correct
answer. This is also shown in Figure 1 (a), illustrating that it is hard for
the existing solutions (_i.e.,_ MeLLo zhong2023mquake ) to decompose the the
question "_Who is the boss of Tom_ " into appropriate sub-questions. At the
same time, given the fact edit to update the company of Tom from _Amazon
$\rightarrow$ Twitter_, yet after updating Tom’s company, the language model
still possesses outdated knowledge about the facts correlated with the edit,
_e.g.,_ Tom’s current boss _etc_. This leads to knowledge inconsistency and
has a detrimental impact on the reliability of KE methods.

To address these limitations, in this work, we propose a novel method, _i.e.,_
Rule-Ke: Rule based Knowledge Editing. As shown in Figure 1 (b), Rule-Ke
leverages logic rules to identify the core parts of the _hard question_ and
performs  _correlated knowledge updates_ , _i.e.,_ updating knowledge/facts
correlated with the edit to ensure knowledge consistency for KE, thus
correctly answering the question as: _Elon Musk_. To the best of our
knowledge, Rule-Ke is amongst the initial attempts to employ logic rules to
help augment the knowledge consistency and improve the end-performance of
existing solutions for MQA under KE (both parameter-based and memory-based).

For experimentation, we use an existing benchmark dataset, as well as a newly
curated dataset (Section 5) encompassing a relatively higher proportion of
_hard to decompose_ questions and edits requiring significantly higher
_correlated knowledge updates_. Experimental evaluation shows that Rule-Ke
improves the end performance of existing methods by a significant margin.

To summarize, this paper makes the following key contributions:

  1. 1.

We introduce Rule-Ke, which leverages rule discovery to discover logic rules
that are helpful for _hard to decompose_ multi-hop questions, as well as
performing _correlated knowledge updates_ to update knowledge about facts
correlated with the edits. As a cherry on top, Rule-Ke could augment the
performance of all existing memory-based and parameter-based KE methods.

  2. 2.

To better show the performance of Rule-Ke, we introduce an evaluation
benchmark, _i.e.,_ RKe-eval that, in contrast to existing benchmarks,
encompasses a wide range of _hard to decompose_ multi-hop questions and edits
requiring significant _correlated knowledge updates_.

  3. 3.

We perform an intensive and extensive experimental evaluation to showcase the
potential of our proposed approach, showing that Rule-Ke can augment the
performance of existing solutions for MQA under KE by up to 92% and 112.9% for
parameter-based and memory-based systems respectively.

##  2 Related Work

Parameter-based KE. These methods can be further classified into fine-tuning,
locating and editing, and meta-learning. Fine-tuning approaches fine-tune the
model parameters or use an auxiliary set of parameters to augment the model’s
knowledge. These methods perform poorly in the KE problems because of
vulnerability to catastrophic forgetting Chen2020RecallAL ; Zhu2020ModifyingMI
. The locate and edit approaches consider the layers of a feed-forward network
as the primary knowledge repositories and update their parameters to inject
new knowledge. This approach was initially proposed in ROME meng2022locating
targeting single edit, which is later extended to a large number of edits by
MEMIT meng2022mass . Huang et al., Huang2024SeeTU  emphasized the need for
generalization across different contexts in the sub-questions. WILKE
Hu2024WilKEWK  uses a dynamic localization KE method to facilitate lifelong
editing. Li et al., Li2023PMETPM  proposed PMET to precisely update the
weights of the feed-forward network. Meta-learning approaches treat the
editing task as a machine learning problem. Some examples include: hyper-
network trained with constrained optimization for fact-only modification
DeCao2021EditingFK , context-aware meta-learned loss scaling by Hu et al.,
Hu2023MetaLearningOA , belief-graph by Hase et al.,Hase2021DoLM . The end goal
of the parameter-editing approaches is to develop an updated model by
integrating information about new data/knowledge.

These models perform poorly for multi-hop question-answering, because each
multi-hop question may invoke a series of inter-dependent sub-questions (with
corresponding fact edits), which makes it harder for the parameter-based
approaches to look for updated responses for individual sub-questions followed
by coordinated reasoning required to generate the final answer.

Memory-based KE. These techniques store edits in an explicit memory and use
retrieval-augmented methods to retrieve the subset of edits relevant to the
question. For instance, Mitchell et al., Mitchell2022MemoryBasedME  proposed
SERAC, a semi-parametric editing method coupled with retrieval-augmented
counter-factual model. Cheng et al., Zheng2023CanWE  employed in-context
learning based on three types of demonstrations (copy, update, and retain) to
edit the model’s knowledge. Han et al., han-etal-2023-improving  developed an
editing retrieval framework to promote the efficacy of model editing methods
during sequential edits. Zhong et al., zhong2023mquake  proposed MeLLo that
uses plan-and-solve paradigm along with self-checking to check whether the
retrieved edit is relevant to the question. Gu et al., gu2023pokemqa  proposed
PokeMQA, a two-stage retrieval by decoupling sub-question decomposition from
knowledge editing. TEMPLE-MQA cheng2024multi  transforms the multi-hop
questions and edits into a structured form, effectively improving the accuracy
of retrieval of relevant edits while addressing the challenge of temporal
knowledge editing.

These methods primarily rely on the plan-and-solve paradigm, _i.e.,_ using
existing LLMs to decompose the question into sub-questions, later, use an
inference plan for response/answer generation. They perform poorly on _hard to
decompose_ multi-hop questions, which limits their ability to ensure knowledge
consistency followed by knowledge edits. This has a detrimental impact on the
end-performance of MQA under KE systems.

Logical Rules for Knowledge Graph Reasoning. Logical rules have extensively
been studied for the knowledge graph reasoning tasks. Quinlan et al.,
Quinlan1990LearningLD  used inductive logic programming to derive logical
rules from training samples in the knowledge graph. RNNLogic Qu2020RNNLogicLL
trains rule generator and reasoning predictor to generate high-quality logic
rules. While most of the above-mentioned works focus on mining rules from the
knowledge graph triples, RuLE by Tang et al., Tang2022RulENK  focuses on the
setting where rules are provided beforehand and leverages these provided rules
to augment the inference performance of the model. Lajus et al.,
Lajus2020FastAE  proposed a rule mining system AMIE-3, which employs a range
of pruning strategies and optimization methods to enable fast and accurate
rule mining. So far, we are not aware of any work using logic rules for
knowledge editing systems.

To summarize, we argue that in contrast to the existing work, Rule-Ke
leverages rule discovery to infer logic rules that are helpful in inferring
new knowledge based on the correlation between the given edit and the model’s
prior knowledge. This makes Rule-Ke a better choice to ensure knowledge
consistency, which is helpful in augmenting the performance of existing
solutions for MQA under KE for both parameter-based and memory-based settings.

##  3 Preliminaries

In this section, we introduce the notations, provide the motivation to use
logical rules for Rule-Ke, and define our problem.

Notations. We use
$\mathcal{K}_{base}=\\{r(s,o)|s,o\in\mathcal{E},r\in\mathcal{R}\\}$ to
represent the knowledge base, where $s$ represents the subject entity and $o$
represent the object entity of the relation $r$, $\mathcal{E}$ represents the
set of entities and $\mathcal{R}$ represents set of relations. We use
$e=r(s,o\rightarrow o^{*})$ to represent an individual knowledge edit,
denoting that object of the subject $s$ with relation $r$ is updated from $o$
to $o^{*}$. A collection of $n$ edits is represented by
$\mathcal{M}=\\{e_{1},e_{2},\cdots,e_{n}\\}$. We use $f$ to represent a
language model and use $Q$ to represent a multi-hop question. Each $Q$
requires multiple reasoning steps to obtain the final answer, where the
reasoning steps form a knowledge path $\mathcal{P}_{Q}=\langle
r_{1}(s_{1},o_{1}),\cdots,r_{n}(s_{n},o_{n})\rangle$ with $o_{n}$ as the final
answer. If one of the fact $r_{i}(s_{i},o_{i})\in\mathcal{P}_{Q}$ is updated
by an edit $e_{i}=r_{i}(s_{i},o_{i}\rightarrow o_{i}^{*})\in\mathcal{M}$, the
resulting knowledge path becomes: $\mathcal{P}^{*}_{Q}=\langle
r_{1}(s_{1},o_{1}),\cdots,r_{i}(s_{i},o_{i}^{*}),\cdots,r_{n}(s_{n}^{*},o_{n}^{*})\rangle$,
_i.e.,_ the subsequent knowledge path will be changed, yielding $o_{n}^{*}$ as
the new answer for question $Q$. It’s notable that $Q$ may be modified by
multiple edits in $\mathcal{M}$.

We use $\varphi:X\rightarrow{p_{0}}$ to represent a logic rule, where $X$ is a
conjunction of predicates representing pre-condition, and $p_{0}$ is a
predicate representing consequence. In this work, we use compositional logic
rules of the form:

$\varphi(r_{h},\textbf{r}_{\textbf{b}}):r_{b_{1}}(z_{0},z_{1})\land
r_{b_{2}}(z_{1},z_{2})\land\cdots\land r_{b_{n}}(z_{n-1},z_{n})\rightarrow
r_{h}(z_{0},z_{n})$ (1)

where $\textbf{r}_{\textbf{b}}=\\{r_{b_{1}},\cdots,r_{b_{n}}\\}$ is a set of
relations for pre-condition, and $r_{h}$ is a relation for consequence,
$\\{z_{0},\cdots,z_{n}\\}$ is a set of variables. When these variables are
replaced with specific entities, we can get a grounding of rules. For example:
_father $\\_$is(Tom,John) $\wedge$ wife$\\_$is(John,Amy) $\rightarrow$
mother$\\_$is(Tom,Amy)_. This grounding illustrates that if Tom’s father is
John and John’s wife is Amy, then it implies Tom’s mother is Amy.

Motivation of Logic Rules. The motivation for employing logic rules for Rule-
Ke stems from the fact that an individual edit $e=r(s,o\rightarrow o^{*})$ not
only affects the knowledge path of $Q$, but may also initiate new knowledge
edits $e^{\prime}$. For instance, an edit _$e$ =company$\\_$is(Tom,Amazon
$\rightarrow$ Twitter)_ will also trigger _$e^{{}^{\prime}}$
=boss$\\_$is(Tom,Jeff Bezos $\rightarrow$ Elon Musk)_. For such cases, logic
rules provide an effective mechanism to capture and represent these
associations among edits more explicitly, which makes them an ideal choice for
Rule-Ke. We call this phenomenon as _correlated knowledge updates_ for edit
$e$ in the rest of this paper. Note that this issue has been overlooked by
previous research on KE.

Problem Definition. MQA under KE aims to inject new knowledge $\mathcal{M}$
into the language model $f$ to come up with an updated model $f^{*}$ to be
used to answer multi-hop questions $Q$. For this, we first use rule discovery
tools to discover the logic rules
$\Sigma=\\{\varphi_{1},\varphi_{2},\cdots\,\varphi_{m}\\}$ from existing
knowledge-base $\mathcal{K}_{base}$. Later, we use these rules $\Sigma$ in
relation with the edit information $\mathcal{M}$ to discover the knowledge
updates correlated with the edits as augmented knowledge
$\mathcal{K}^{{}^{\prime}}$. Finally, we use the $\mathcal{K}^{{}^{\prime}}$
along with $\mathcal{M}$ to perform knowledge editing for existing methods in
a performance-enhanced fashion.

##  4 Rule-Ke: Rule Based Knowldege Editing

The core idea of Rule-Ke is to leverage logical rules to infer new/updated
knowledge, resulting in a correlation between requested knowledge edits and
prior knowledge. Its workflow is explained as follows.

###  4.1 Workflow of Rule-Ke

The overall workflow of Rule-Ke is shown in Figure 2. It could be explained as
a three-step process: (a) Discover logic rules $\Sigma$ from a large-scale
knowledge base $\mathcal{K}_{base}$. (b) For each edit $e\in\mathcal{M}$,
determine the subset of rules correlated by the edit $e$, _i.e.,_
$\Sigma_{e}\subseteq\Sigma$. (c) Use correlated rules $(\Sigma_{e})$ to infer
and/or correlated knowledge to be stored as augmented knowledge
$\mathcal{K}^{{}^{\prime}}$, later used for knowledge consistency of KE
methods.

Step a: Mining Logic Rules. The first step of Rule-Ke is the rule mining
process. It aims at excavating the common logic rules $\Sigma$ from the large-
scale knowledge base $\mathcal{K}_{base}$, facilitating subsequent prediction
of the _correlated knowledge_ affected by the edits. For this, we use Wikidata
2014wikidata  as our knowledge base. The quality of the discovered rules
varies and is not always valid in all situations. In order to avoid redundant
rules, we use support threshold $\mathcal{A}_{\Sigma}$ as a quantitative
metric, indicative of the quality of the rule.

There are many works that study rule mining and achieve excellent results,
such as AMIE-3 Lajus2020FastAE  and RNNLogic Qu2020RNNLogicLL . Thus, we use
the existing tools to mine logic rules and their corresponding support
threshold from $\mathcal{K}_{base}$, as follows:

$\Sigma,\mathcal{A}_{\Sigma}=\text{Tool${}_{\text{mine}}$}(\mathcal{K}_{base}),$
(2)

where $\Sigma=\\{\varphi_{1},\varphi_{2},\cdots\,\varphi_{m}\\}$ is a set of
rules,
$\mathcal{A}_{\Sigma}=\\{\alpha_{\varphi_{1}},\alpha_{\varphi_{2}},\cdots,\alpha_{\varphi_{m}}\\}$
is a set of support thresholds, with $\alpha_{\varphi_{i}}\in[0,1]$ indicating
the likelihood of the rule $\varphi_{i}$ to be true. We use AMIE-3 as our rule
mining tool $(\text{Tool${}_{\text{mine}}$})$, as it has the ability to mine
higher-quality rules in practice.

Step b: Determining correlated Rules. Editing not only affects single
knowledge but may trigger changes in the entire knowledge system, causing its
related knowledge to be updated accordingly. The logic rules serve as a bridge
between an edit and its correlated knowledge, thus, determining the relevant
bridge for each edit is very important. The objective of this step is to find
a subset of relevant rules $\Sigma_{e}\subseteq\Sigma$ for each edit
$e\in\mathcal{M}$. To determine the subset of rules that are relevant to an
edit, we use the semantic similarity between the relation part of the edit and
the relations in the pre-conditional part of the rule as a selection
criterion. For instance, given an edit "_work $\\_$for (Tom, Apple)
$\rightarrow$ Twitter_", and a set of rules: {"_company $\\_$is
($z_{0}$,$z_{1}$) $\land$ owner$\\_$is ($z_{1}$,$z_{2}$) $\rightarrow$
boss$\\_$is ($z_{0}$,$z_{2}$)_"; "_born $\\_$in ($z_{0}$,$z_{1}$) $\land$
locate$\\_$in ($z_{1}$,$z_{2}$) $\rightarrow$ raised$\\_$in
($z_{0}$,$z_{2}$)_"}, the relation part of the edit "_work $\\_$for_" has
higher semantic relevance with the relation "_company $\\_$is_" compared to
other relations, _e.g.,_ "owner_is", "born_in" _etc_.

To implement our above intuition, we followed the idea of dense retrieval
Karpukhin2020DensePR  to contrast the semantic relevance based on the vector
similarity of the relation embeddings. For this, we use an encoder $E$ to
encode the relation $r$ of the edit $e$ and the relation set $\mathbf{r_{b}}$
of rule $\varphi{(r_{h},\mathbf{r_{b}})}$, as shown below:

$\displaystyle v_{e}$ $\displaystyle=E(r),$ (3)
$\displaystyle\mathbf{V}_{\varphi}$
$\displaystyle=E(\mathbf{r_{b}})=\\{E(r_{b_{1}}),\cdots,E(r_{b_{n}})\\},$

where $v_{e}$ is the vector embedding for relation $r$ of edit $e$,
$\mathbf{V}_{\varphi}$ is the set of vector embedding for the relation set
$\mathbf{r_{b}}$ of $\varphi$. Later, we use cosine similarity (sim) for the
elements of $\mathbf{V}_{\varphi}$ and $v_{e}$ to determine the relational
predicate exhibiting maximum similarity with relation $r$, as shown below.

$v^{*}_{k}=\operatorname*{arg\,max}_{v_{k}\in\mathbf{V}_{\varphi}}{(\text{sim}(v_{k},v_{e}))},$
(4)

where $v^{*}_{k}$ is the embedding vector of the predicate relation
$r_{b_{k}}$ with highest similarity with $v_{e}$.

Because the quality of rule $\varphi$ may not be high and correlated knowledge
found by low-quality rules is not necessarily reliable, we use
$\alpha_{\varphi}$ times scaled similarity of $v^{*}_{k}$ and $v_{e}$ compared
against the correlation threshold $\delta$ to determine whether
$\varphi_{i}(r_{h},\mathbf{r_{b}})$ is a reliable rule for predicting
correlated knowledge for subsequent steps:

Figure 2: The overall workflow of Rule-Ke. It encompasses: (a) rule mining,
(b) determining correlated rules, and (c) inferring correlated knowledge.

$\psi:(v^{*}_{k}\cdot v_{e})*\alpha_{\varphi}>\delta,$ (5)

where $\psi$ returns a logical indicator of whether the the statement is true
or not. Finally, we use the above process to find all the logic rules
$\varphi{(r_{h},\mathbf{r_{b}})\in\Sigma}$ which satisfy corresponding $\psi$
is true, and combine them into the rule subset $\Sigma_{e}$, _i.e.,_ a set of
rules activated by edit $e$.

Step c: Inferring Correlated Knowledge. After selecting the subset of rules
$\Sigma_{e}$ corresponding to the relation in the edit $e\in\mathcal{M}$, we
need to infer _correlated knowledge_ for edit $e$. Suppose the rule is
activated at position $k$, _i.e.,_ at pre-conditional predicate $r_{b_{k}}$,
we can instantiate variables $z_{k-1}$ and $z_{k}$ as $s$ and $o^{*}$,
respectively, as shown below.

$r_{b_{1}}(\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}\mathbf{z_{0}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0},z_{1})\land
r_{b_{2}}(z_{1},z_{2})\cdots\underbrace{r_{b_{k}}(z_{k-1}(s),z_{k}(o^{*}))}_{\textsc{New
Knowledge}}\cdots\land
r_{b_{n}}(z_{n-1},\color[rgb]{.75,.5,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.5,.25}\mathbf{z_{n}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0})\rightarrow\underbrace{r_{h}(\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}\mathbf{z_{0}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0},\color[rgb]{.75,.5,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.5,.25}\mathbf{z_{n}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0})}_{\textsc{correlated
Knowledge}}.$ (6)

The above equation shows how the _correlated knowledge_ is generated from the
rule $\varphi$ and edit $e$. However, we only know $z_{k-1}=s$ and
$z_{k}=o^{*}$. Thus, we need to find the specific entity for variable
$\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}\mathbf{z_{0}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$
and
$\color[rgb]{.75,.5,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.5,.25}\mathbf{z_{n}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$
to determine
$r_{h}(\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}\mathbf{z_{0}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0},\color[rgb]{.75,.5,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.5,.25}\mathbf{z_{n}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0})$
as the _correlated knowledge_. For this, we use: (i) back tracking to
determine the
$\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}\mathbf{z_{0}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$;
and (ii) forward tracking to determine the
$\color[rgb]{.75,.5,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.5,.25}\mathbf{z_{n}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$,
with corresponding chain shown in (7).

$\underbrace{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}\mathbf{z_{0}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0},z_{1},\cdots,z_{k-1}(s)}_{\textsc{Back
Tracking}\leftarrow},\underbrace{z_{k}(o^{*}),\cdots,z_{n-1},\color[rgb]{.75,.5,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.5,.25}\mathbf{z_{n}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}_{\rightarrow\textsc{Forward
Tracking}}.$ (7)

The process flows of forward tracking and backward tracking are explained as
follows.

Forward Tracking is an iterative process used to determine the specific entity
for the last variable
$\color[rgb]{.75,.5,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.5,.25}\mathbf{z_{n}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$
by traversing the chain
$(z_{k}(o^{*}),\cdots,z_{n-1},\color[rgb]{.75,.5,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.5,.25}\mathbf{z_{n}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0})$
in the forward direction for one step at a time, with only prior knowledge
about the specific entity $o^{*}$ for $z_{k}$. Each step of this iterative
process assumes that we aim to determine the specific entity of variable
$z_{m+1}$ based on $r_{b_{m+1}}(z_{m}(o_{z_{m}}),z_{m+1})$, where $o_{z_{m}}$
is the specific entity for $z_{m}$, and $m$ indicates the current iterative
position $k\leq m\leq n-1$.

It is easy to find that each step corresponds to a single-hop question.
However, this question may be modified by the existing edits. Thus, we need to
query the edit memory if there are related edits based on $o_{z_{m}}$ and
$r_{b_{m+1}}$. For this, we use dense retrieval Karpukhin2020DensePR  to
determine the corresponding edit, with details provided in Appendix B.

For the cases, we are unable to find the relevant edit in edit memory, we will
query a language model to infer the specific entity for variable $z_{m+1}$.
For this, we design an in-context learning prompt (explained in Appendix A)
that prompts an LLM as follows.

$o_{z_{m+1}}=\text{LLM}(\text{P}_{\text{forward}}(o_{z_{m}},r_{b_{m+1}})),$
(8)

where $\text{P}_{\text{forward}}$ is the in-context prompt for $o_{z_{m}}$ and
relation $r_{b_{m+1}}$ used as input for LLM, yielding $o_{z_{m+1}}$ as
specific entity for variable $z_{m+1}$. We can finally get the specific entity
for
$\color[rgb]{.75,.5,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.5,.25}\mathbf{z_{n}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$
by iterating the above process.

Back Tracking is similar to forward tracking. The primary difference is that
it traverses the chain
$(\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}\mathbf{z_{0}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0},\cdots,z_{k-1}(s))$
in the reverse direction in order to infer the specific entity for
$\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}\mathbf{z_{0}}$.
Specifically, each step of this process assumes that we aim to determine the
specific entity of variable $z_{j-1}$ based on
$r_{b_{j}}(z_{j-1},z_{j}(o_{z_{j}}))$, where $o_{z_{j}}$ is the specific
entity for $z_{j}$, and $j$ indicating the current iterative position and
$1\leq j\leq k-1$.

Here again, similar to the forward tracking, we first look for relevant edits
in the edit memory helpful in inferring $z_{j-1}$ based on $o_{z_{j}}$ and
$r_{b_{j}}$. This is explained in detail in Appendix B. For the cases where we
are unable to find relevant edits, we infer $z_{j-1}$ by querying the language
model. For this, we construct an in-context learning prompt that prompts LLM
to infer $z_{j-1}$:

$o_{z_{j-1}}=\text{LLM}(\text{P}_{\text{back}}(r_{b_{j}},o_{z_{j}}))$ (9)

where $\text{P}_{\text{back}}$ is the in-context prompt that uses $r_{b_{j}}$
and $z_{j}$ as input and prompts LLM, to yield $o_{z_{j-1}}$ as specifc entity
for $z_{j-1}$, for details refer to Appendix A.

Finally, we use the start point
$\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}\mathbf{z_{0}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$
and endpoint
$\color[rgb]{.75,.5,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.5,.25}\mathbf{z_{n}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$
resulting from backward tracking and forward tracking to infer the correlated
knowledge
$r_{h}(\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}\mathbf{z_{0}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0},\color[rgb]{.75,.5,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.5,.25}\mathbf{z_{n}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0})$
to be inserted in $\mathcal{K}^{{}^{\prime}}$.

###  4.2 Rule-Ke— _A cherry on the Top_

Existing KE methods can not maintain knowledge consistency effectively. The
augmented knowledge $\mathcal{K}^{{}^{\prime}}$ can help to alleviate this
problem because it is generated from the interactions between edits
$\mathcal{M}$ and logic rules $\Sigma$. In order to adapt Rule-Ke to
downstream KE methods, we need to transform the knowledge in
$\mathcal{K}^{{}^{\prime}}$ from knowledge to edits, _i.e.,_ from $r(s,o)$ to
$r(s,o\rightarrow o^{*})$. Specifically, we define a new set of edits based on
$\mathcal{K}^{{}^{\prime}}$ as follows:

$\mathcal{M}_{\mathcal{K}^{{}^{\prime}}}=\\{r(s,\text{null}\rightarrow o)\mid
r(s,o)\in\mathcal{K}^{{}^{\prime}}\\},$ (10)

where null is a specific placeholder, meaning that we no longer need the
information about the original object. We then merge the newly curated edit
set $\mathcal{M}_{\mathcal{K}^{{}^{\prime}}}$ with $\mathcal{M}$ to come up
with $\mathcal{M}_{\text{AUG}}$, _i.e.,_
$\mathcal{M}_{\text{AUG}}=\mathcal{M}\cup\mathcal{M}_{\mathcal{K}^{{}^{\prime}}}$
as the final set of knowledge edits. Finally, we leverage
$\mathcal{M}_{\text{AUG}}$ to further edit the model’s knowledge/information
for parameter-based methods, whereas for memory-based methods, we can store
$\mathcal{M}_{\text{AUG}}$ in the edit memory, thus allowing the model to
generate the correct response for correlated knowledge instances.

##  5 RKe-eval: Rule-Ke Evaluation benchmark

We observe that existing benchmarks for MQA under KE, _e.g.,_ MQuAKE
zhong2023mquake , are not an ideal option to rigorously test the ability to
maintain knowledge consistency for editing methods. The majority of the data
in MQuAKE can easily be decomposed into multiple independent knowledge
sequences/units, which can be answered independently to come up with the final
answer. This severely undermines the end-utility of existing benchmarks for
analyzing: (i) hard-to-decompose questions, and (ii) correlation among
knowledge updates, _i.e.,_ how an individual knowledge update may impact the
knowledge for the subsequent parts.

Figure 3: Four different scenarios of new knowledge generated by logic rules
and edits for RKe-eval.

In order to better evaluate the knowledge consistency of Rule-Ke and existing
methods on MQA under KE for "_hard questions_ " and "_correlated knowledge
updates_ ", we propose a new evaluation benchmark, namely: RuleKe-Evaluation
(RKe-eval). RKe-eval encompasses numerous multi-hop questions and 17 different
rules with pre-condition of length 2. Each multi-hop question is associated
with a unique rule and at least one edit. As shown in Figure 3, we categorize
the knowledge inferred in RKe-eval into four different scenarios: (i) No-Edit:
the knowledge of the rule part is not modified by edit. (ii) Right-Edit: only
the second part of the rule knowledge is modified by edit and requires back
tracking to answer this question. (iii) Left-Edit: only the first part of the
rule knowledge is modified by edit and requires forward tracking to answer
this question. (iv) Both-Edit: all the knowledge of the rule part is modified
by edit. The process flow of data curation is explained in detail in Appendix
C, along with an example illustration in Appendix Table 4. This categorization
method comprehensively covers all scenarios where new knowledge is generated
due to edits and corresponding logic rules.

##  6 Experiments

###  6.1 Experimental Settings

Datasets. We evaluate the performance of Rule-Ke using an existing knowledge
editing benchmark MQuAKE-CF-3K zhong2023mquake  and our proposed dataset RKe-
eval. Detailed descriptions and statistics of these datasets are provided in
Appendix D.1.

Evaluation Metrics. We use multi-hop accuracy (Acc) zhong2023mquake  as an
evaluation metric. Each instance in MQuAKE-CF-3K include three multi-hop
questions. An instance is considered correct if any of the three multi-hop
questions is answered correctly. Mathematical formulation and further details
about the evaluation metrics are given in Appendix D.4. Note that just for
simplification, we do not use hop-wise accuracy gu2023pokemqa  as a metric
because our method primarily relies on the final response rather than the
evaluating the intermediate path.

Baseline methods. For performance evaluation of Rule-Ke, we use both
parameter-based and memory-based KE methods as baselines. The parameter-based
baselines include: Fine-tuning (FT) Zhu2020ModifyingMI , ROME meng2022locating
and MEMIT meng2022mass . The memory-based baselines include MeLLo
zhong2023mquake , PokeMQA gu2023pokemqa  and TEMPLE-MQA cheng2024multi .
Details about the baseline models are provided in Appendix D.3.

Experimental Setup. To assess performance across different number of edits, we
conduct stratified sampling based on the number of hops, which allows us to
construct batches of different sizes. The setting of different batch sizes is
denoted as $k$-E $(k\in\\{1,100,All\\})$. The value of the correlation
threshold $\delta$ is 0.8. The value of $\theta$ in Appendix B is 0.7. We
conduct experiments on the three language models, _i.e.,_ LLaMa-2-7B
Touvron2023Llama2O , LLaMa-2-7B-chat Touvron2023Llama2O  and GPT-
turbo-3.5-instruct Ouyang2022TrainingLM . Further details about these models
are given in Appendix D.2. We evaluate all the methods in the
$\\{1,100,All\\}$-E setting. All experiments are performed using PyTorch 2.1.0
with two A40-48GB GPUs. All the results reported in the paper are averaged
over three runs.

###  6.2 Experimental Results

####  Rule-Ke can boost the performance of memory-based methods.

We first analyze the impact of Rule-Ke in augmenting the performance of
memory-based methods. Corresponding results in Table 1 show that Rule-Ke
consistently augments the performance of the memory-based methods,
outperforming the original models by a significant margin.

Considering the results of our model using LLaMa-2-7B, Rule-Ke improves the
performance by up to {112.92%, 106.31%, and 95.20%} for RKe-eval, and {12.13%,
2.30%, and 2.03%} for MQuAKE compared to the best-performing original variants
under {1, 100, and All}-E settings respectively. The results of variants for
Rule-Ke using GPT-turbo-3.5-instruct exhibit a similar trend. Such drastic
improvement in performance showcases the logical generalization abilities of
Rule-Ke, ensuring knowledge consistency for MQA under KE.

We can also observe that as the size of the edit batch increases, the
improvement of performance decreases gradually compared to smaller edit
batches. A key justification in this regard is the fact that logic rules
leveraged by Rule-Ke generate additional knowledge edits, thus increasing the
size of the edit memory by more than three-fold, which makes it cumbersome for
the retrieval to find the right edit from the edit memory. Nevertheless, this
issue could be mitigated by using robust retrieval systems. For instance,
TEMPLE-MQA cheng2024multi , with a better retrieval performance, outperforms
MeLLo and PokeMQA in the 100/all-E scenario on RKe-eval.

AUG | Method | LLaMa-2-7B | GPT-3.5-turbo-instruct
---|---|---|---
MQuAKE-CF-3K | RKe-eval | MQuAKE-CF-3K | RKe-eval
1-E | 100-E | All-E | 1-E | 100-E | All-E | 1-E | 100-E | All-E | 1-E | 100-E | All-E
Original | MeLLo | 36.13 | 28.50 | 21.33 | 18.24 | 13.84 | 2.03 | 59.67 | 41.47 | 35.81 | 29.05 | 23.73 | 10.14
PoKeMQA | 39.13 | 29.33 | 22.83 | 19.81 | 14.82 | 3.81 | 66.18 | 55.89 | 47.42 | 32.05 | 25.18 | 13.81
TEMPLE-MQA | 46.67 | 43.95 | 41.33 | 16.54 | 15.84 | 14.19 | 75.08 | 66.02 | 53.12 | 37.29 | 35.97 | 33.56
Rule-Ke | MeLLo | 51.33 | 30.28 | 26.13 | 41.22 | 16.27 | 14.26 | 69.33 | 52.71 | 42.06 | 62.51 | 45.65 | 32.43
PoKeMQA | 51.17 | 29.71 | 27.91 | 42.18 | 19.71 | 16.83 | 73.41 | 60.95 | 52.38 | 63.61 | 47.41 | 37.72
TEMPLE-MQA | 52.33 | 44.96 | 42.17 | 38.79 | 32.68 | 27.70 | 80.73 | 69.06 | 58.03 | 65.21 | 61.18 | 54.68

Table 1: Results for memory-based methods, _i.e.,_ original and augmented with
Rule-Ke on the MQuAKE-CF-3K and RKe-eval. We use multi-hop accuracy (Acc) as
the evaluation metric. The best scores are bold-faced, with the best results
among the original models underlined. "E" indicates edit batch size and "AUG"
indicates the knowledge augmentation methods. The symbols have the same
meaning in the following tables.

AUG | Method | LLaMa-2-7B-chat
---|---|---
MQuAKE-CF-3K | RKe-eval
1-E | 100-E | All-E | 1-E | 100-E | All-E
Original | FT | 8.62 | 3.34 | 0.34 | 3.62 | 2.05 | 0.29
ROME | 7.42 | 2.14 | 0.22 | 11.39 | 4.64 | 0.38
MEMIT | 14.33 | 12.17 | 0.59 | 15.14 | 5.65 | 0.54
Rule-Ke | FT | 9.89 | 3.62 | 0.42 | 11.82 | 2.66 | 0.52
ROME | 9.35 | 2.14 | 0.31 | 22.02 | 7.02 | 0.40
MEMIT | 18.67 | 15.31 | 0.77 | 29.07 | 10.19 | 0.95

Figure 4: Results of parameter-based methods on MQuAKE-CF-3K and RKe-eval. We
use multi-hop accuracy (Acc) as the evaluation metric.

Rule-Ke improves knowledge consistency for parameter-based methods. We also
analyze the impact of Rule-Ke on the parameter-based methods. Corresponding
results in Figure 4 show that for {1,100,All}-E, Rule-Ke improves the
performance of the parameter-based methods by {30.29%, 25.80%, and 30.50% } on
MQuAKE-CF-3K; {92.00%, 80.35%, and 75.93% } on RKe-eval respectively. Its
impact is more evident for MEMIT meng2022mass , which yields a stable
improvement in performance even under a large number of edits. Overall, these
results indicate that Rule-Ke is able to solve some of the key limitations of
parameter-based KE methods on MQA under KE, highlighted in previous work
zhong2023mquake ; gu2023pokemqa .

Correlating these results, we observe that for a large number of edits, the
performance of parameter-based systems degrade more compared to that of the
memory-based methods. This finding is also consistent with the previous
research cheng2024multi .

Back tracking is more challenging than forward tracking. We also analyze the
impact of Rule-Ke on multiple different scenarios of RKe-eval, explained in
Section 5. Results in Figure 5 (a) show that compared to the original method,
the performance improvement incurred by Rule-Ke is more prominent for
Left/Both-Edit situations compared to that of No/Right-Edit situations. An
underlying reason in this regard is the fact that the Right-Edit situation
requires the process of back tracking, indicating relatively lower success
rate than that of forward tracking. To further explore this phenomenon, we
examined some failing cases with back tracking and found that it is primarily
caused by many-to-1 relations, _e.g.,_ for the question "_Who holds the
nationality of America?_ " there are many people who match this question.

To our surprise, for No-Edit situation (_i.e.,_ no knowledge edits involved),
using Rule-Ke leads to slight decrease in accuracy. A probable justification
in this regard is the fact that the incorporation of additional knowledge in
the edit memory deteriorated the retrieval performance, resulting in a
decrease in the overall accuracy of the end model.

Influence of the correlation threshold. The correlation threshold $\delta$ in
Equation (5), plays a crucial role in controlling the final amount and quality
of additional knowledge generated by Rule-Ke. Thus, we conduct experiments to
explore the influence of different values of $\delta$ using the variant of
Rule-Ke using LLama-2 and RKe-eval. The results in Figure 5 (b) and (c) show
that Rule-Ke yields the best possible performance for value of $\delta$ = 0.8,
while augmenting the size of edit memory by approximately 3.9$\times$ times.

We also observe that increasing the value of $\delta$ beyond 0.8 will
significantly decrease the number of activated rules $\Sigma_{e}$ for each
edit $e$, which in turn limits the amount of newly generated knowledge
correlated with the edits, thus deteriorating the end-performance of Rule-Ke.
On the other hand, decreasing the value of $\delta$ results in an increased
number of activated rules $\Sigma_{e}$, yielding surplus amount of augmented
knowledge. This will also limit the retrieval accuracy of memory-based
methods. Overall, higher values of $\delta$ have a more detrimental impact on
the performance compared to the lower ones.

Figure 5: (a) Avg., multi-hop accuracy (Acc) for memory-based methods for
different inferred situations in RKe-eval. (b) Increase in size of the edit
memory as a multiplier of original size with varying threshold $(\delta)$, for
all methods. (c) Multi-hop accuracy (Acc) for Rule-Ke using RKe-eval against
different values of threshold $(\delta)$. All results are computed using
LLama-2-7B-chat.

Figure 6: (a) Execution time of Rule-Ke with parameter-based methods using
RKe-eval and LLama-2-7B under varying edit batch sizes. (b) Execution time
overhead of Rule-Ke with memory-based methods using RKe-eval and
GPT-3.5-turbo-instruct under varying edit batch sizes.

Efficiency analysis of Rule-Ke. Finally, we conduct experiments to explore the
efficiency of Rule-Ke. Note that for these results, we ignore the time it
takes to mine the logic rules, as this process is used only once, _i.e.,_ only
at the start of model training.

Figure 6 (a) shows that for the original variants of parameter-based methods,
the running time increases with the increase in the number of edits. However,
the increase in the execution time incurred by Rule-Ke is almost negligible
for edits with different batch sizes. The results in Figure 6 (b) show that
for the original variants of the memory-based methods, the execution time is
almost not impacted by the edit batch size and is primarily upper-bounded by
API calls and/or model inference time. For the model augmented by Rule-Ke, the
execution time increases by 1.6 folds and 4 folds under 100-E and All-E
settings compared to that of 1-E, respectively.

Overall, these results show that although for some cases, the running time of
Rule-Ke is slightly higher than the original variants, it is still within the
acceptable range while, at the same time, the end model offers significant
improvements in the performance.

##  7 Conclusion

In this paper, we proposed Rule-Ke that leverages logic rules for knowledge
consistency in order to perform knowledge editing in a performance-enhanced
fashion. Rule-Ke is a plug-and-play framework that can be used with existing
MQA methods under KE as a _cherry on the top_. Experimental results using a
benchmark and our newly curated data set showed that Rule-Ke can augment the
performance of existing methods on MQA under KE by a significant margin.

## References

  * [1] Muhammad Asif Ali, Zhengping Li, Shu Yang, Keyuan Cheng, Yang Cao, Tianhao Huang, Lijie Hu, Lu Yu, and Di Wang.  Prompt-saw: Leveraging relation-aware graphs for textual prompt compression.  arXiv preprint arXiv:2404.00489, 2024.
  * [2] Nicola De Cao, Wilker Aziz, and Ivan Titov.  Editing factual knowledge in language models.  In Conference on Empirical Methods in Natural Language Processing, 2021.
  * [3] Sanyuan Chen, Yutai Hou, Yiming Cui, Wanxiang Che, Ting Liu, and Xiangzhan Yu.  Recall and learn: Fine-tuning deep pretrained language models with less forgetting.  In Conference on Empirical Methods in Natural Language Processing, 2020.
  * [4] Keyuan Cheng, Gang Lin, Haoyang Fei, Lu Yu, Muhammad Asif Ali, Lijie Hu, Di Wang, et al.  Multi-hop question answering under temporal knowledge editing.  arXiv preprint arXiv:2404.00492, 2024.
  * [5] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265–284. Springer, 2006.
  * [6] Hengrui Gu, Kaixiong Zhou, Xiaotian Han, Ninghao Liu, Ruobing Wang, and Xin Wang.  Pokemqa: Programmable knowledge editing for multi-hop question answering.  arXiv preprint arXiv:2312.15194, 2023.
  * [7] Xiaoqi Han, Ru Li, Hongye Tan, Wang Yuanlong, Qinghua Chai, and Jeff Pan.  Improving sequential model editing with fact retrieval.  In Houda Bouamor, Juan Pino, and Kalika Bali, editors, Findings of the Association for Computational Linguistics: EMNLP 2023, pages 11209–11224, Singapore, December 2023. Association for Computational Linguistics.
  * [8] Peter Hase, Mona T. Diab, Asli Celikyilmaz, Xian Li, Zornitsa Kozareva, Veselin Stoyanov, Mohit Bansal, and Srini Iyer.  Do language models have beliefs? methods for detecting, updating, and visualizing model beliefs.  ArXiv, abs/2111.13654, 2021.
  * [9] Ruixin Hong, Hongming Zhang, Honghui Zhao, Dong Yu, and Changshui Zhang.  Faithful question answering with monte-carlo planning.  In Annual Meeting of the Association for Computational Linguistics, 2023.
  * [10] Chenhui Hu, Pengfei Cao, Yubo Chen, Kang Liu, and Jun Zhao.  Wilke: Wise-layer knowledge editor for lifelong knowledge editing.  ArXiv, abs/2402.10987, 2024.
  * [11] Lijie Hu, Ivan Habernal, Lei Shen, and Di Wang.  Differentially private natural language models: Recent advances and future directions.  arXiv preprint arXiv:2301.09112, 2023.
  * [12] Lijie Hu, Yixin Liu, Ninghao Liu, Mengdi Huai, Lichao Sun, and Di Wang.  Improving faithfulness for vision transformers.  arXiv preprint arXiv:2311.17983, 2023.
  * [13] Lijie Hu, Yixin Liu, Ninghao Liu, Mengdi Huai, Lichao Sun, and Di Wang.  Seat: stable and explainable attention.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37(11), pages 12907–12915, 2023.
  * [14] Lijie Hu, Shuo Ni, Hanshen Xiao, and Di Wang.  High dimensional differentially private stochastic optimization with heavy-tailed data.  In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 227–236, 2022.
  * [15] Lijie Hu, Zihang Xiang, Jiabin Liu, and Di Wang.  Privacy-preserving sparse generalized eigenvalue problem.  In International Conference on Artificial Intelligence and Statistics, pages 5052–5062. PMLR, 2023.
  * [16] Nathan J. Hu, Eric Mitchell, Christopher D. Manning, and Chelsea Finn.  Meta-learning online adaptation of language models.  ArXiv, abs/2305.15076, 2023.
  * [17] Jie Huang and Kevin Chen-Chuan Chang.  Towards reasoning in large language models: A survey.  ArXiv, abs/2212.10403, 2022.
  * [18] Youcheng Huang, Wenqiang Lei, Zheng Zhang, Jiancheng Lv, and Shuicheng Yan.  See the unseen: Better context-consistent knowledge-editing by noises.  ArXiv, abs/2401.07544, 2024.
  * [19] Cheonsu Jeong.  A study on the implementation of generative ai services using an enterprise data-based llm application architecture.  arXiv preprint arXiv:2309.01105, 2023.
  * [20] Vladimir Karpukhin, Barlas Oğuz, Sewon Min, Patrick Lewis, Ledell Yu Wu, Sergey Edunov, Danqi Chen, and Wen tau Yih.  Dense passage retrieval for open-domain question answering.  ArXiv, abs/2004.04906, 2020.
  * [21] Tushar Khot, H. Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal.  Decomposed prompting: A modular approach for solving complex tasks.  ArXiv, abs/2210.02406, 2022.
  * [22] Nikolaos Kolitsas, Octavian-Eugen Ganea, and Thomas Hofmann.  End-to-end neural entity linking.  arXiv preprint arXiv:1808.07699, 2018.
  * [23] Songning Lai, Lijie Hu, Junxiao Wang, Laure Berti-Equille, and Di Wang.  Faithful vision-language interpretation via concept bottleneck models.  In The Twelfth International Conference on Learning Representations, 2023.
  * [24] Jonathan Lajus, Luis Galárraga, and Fabian M. Suchanek.  Fast and exact rule mining with amie 3.  The Semantic Web, 12123:36 – 52, 2020.
  * [25] Yunshi Lan, Gaole He, Jinhao Jiang, Jing Jiang, Wayne Xin Zhao, and Ji rong Wen.  A survey on complex knowledge base question answering: Methods, challenges and solutions.  ArXiv, abs/2105.11644, 2021.
  * [26] Xiaopeng Li, Shasha Li, Shezheng Song, Jing Yang, Jun Ma, and Jie Yu.  Pmet: Precise model editing in a transformer.  ArXiv, abs/2308.08742, 2023.
  * [27] Vaibhav Mavi, Anubhav Jangra, and Adam Jatowt.  A survey on multi-hop question answering and generation.  ArXiv, abs/2204.09140, 2022.
  * [28] Kevin Meng, David Bau, Alex Andonian, and Yonatan Belinkov.  Locating and editing factual associations in gpt.  Advances in Neural Information Processing Systems, 35:17359–17372, 2022.
  * [29] Kevin Meng, Arnab Sen Sharma, Alex J Andonian, Yonatan Belinkov, and David Bau.  Mass-editing memory in a transformer.  In The Eleventh International Conference on Learning Representations, 2022.
  * [30] Eric Mitchell, Charles Lin, Antoine Bosselut, Christopher D. Manning, and Chelsea Finn.  Memory-based model editing at scale.  ArXiv, abs/2206.06520, 2022.
  * [31] Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke E. Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Francis Christiano, Jan Leike, and Ryan J. Lowe.  Training language models to follow instructions with human feedback.  ArXiv, abs/2203.02155, 2022.
  * [32] Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang.  Rnnlogic: Learning logic rules for reasoning on knowledge graphs.  ArXiv, abs/2010.04029, 2020.
  * [33] J. Ross Quinlan.  Learning logical definitions from relations.  Machine Learning, 5:239–266, 1990.
  * [34] Vipula Rawte, Amit Sheth, and Amitava Das.  A survey of hallucination in large foundation models.  arXiv preprint arXiv:2309.05922, 2023.
  * [35] Jinyan Su, Lijie Hu, and Di Wang.  Faster rates of private stochastic convex optimization.  In International Conference on Algorithmic Learning Theory, pages 995–1002. PMLR, 2022.
  * [36] Xiaojuan Tang, Song-Chun Zhu, Yitao Liang, and Muhan Zhang.  Rule: Neural-symbolic knowledge graph reasoning with rule embedding.  ArXiv, abs/2210.14905, 2022.
  * [37] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al.  Llama 2: Open foundation and fine-tuned chat models.  arXiv preprint arXiv:2307.09288, 2023.
  * [38] Denny Vrandečić and Markus Krötzsch.  Wikidata: a free collaborative knowledgebase.  Communications of the ACM, 57(10):78–85, 2014.
  * [39] Di Wang, Jiahao Ding, Lijie Hu, Zejun Xie, Miao Pan, and Jinhui Xu.  Differentially private (gradient) expectation maximization algorithm with statistical guarantees.  arXiv preprint arXiv:2010.13520, 2020.
  * [40] Di Wang, Huangyu Zhang, Marco Gaboardi, and Jinhui Xu.  Estimating smooth glm in non-interactive local differential privacy model with public unlabeled data.  In Algorithmic Learning Theory, pages 1207–1213. PMLR, 2021.
  * [41] Lei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu, Yunshi Lan, Roy Ka-Wei Lee, and Ee-Peng Lim.  Plan-and-solve prompting: Improving zero-shot chain-of-thought reasoning by large language models.  In Annual Meeting of the Association for Computational Linguistics, 2023.
  * [42] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Huai hsin Chi, F. Xia, Quoc Le, and Denny Zhou.  Chain of thought prompting elicits reasoning in large language models.  ArXiv, abs/2201.11903, 2022.
  * [43] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush.  Transformers: State-of-the-art natural language processing.  In Conference on Empirical Methods in Natural Language Processing, 2019.
  * [44] Zihang Xiang, Chenglong Wang, and Di Wang.  How does selection leak privacy: Revisiting private selection and improved results for hyper-parameter tuning.  arXiv preprint arXiv:2402.13087, 2024.
  * [45] Zihang Xiang, Tianhao Wang, Wanyu Lin, and Di Wang.  Practical differentially private and byzantine-resilient federated learning.  Proceedings of the ACM on Management of Data, 1(2):1–26, 2023.
  * [46] Xilie Xu, Keyi Kong, Ning Liu, Lizhen Cui, Di Wang, Jingfeng Zhang, and Mohan Kankanhalli.  An llm can fool itself: A prompt-based adversarial attack.  arXiv preprint arXiv:2310.13345, 2023.
  * [47] Shu Yang, Muhammad Asif Ali, Cheng-Long Wang, Lijie Hu, and Di Wang.  Moral: Moe augmented lora for llms’ lifelong learning.  arXiv preprint arXiv:2402.11260, 2024.
  * [48] Shu Yang, Lijie Hu, Lu Yu, Muhammad Asif Ali, and Di Wang.  Human-ai interactions in the communication era: Autophagy makes large models achieving local optima.  arXiv preprint arXiv:2402.11271, 2024.
  * [49] Shu Yang, Jiayuan Su, Han Jiang, Mengdi Li, Keyuan Cheng, Muhammad Asif Ali, Lijie Hu, and Di Wang.  Dialectical alignment: Resolving the tension of 3h and security threats of llms.  arXiv preprint arXiv:2404.00486, 2024.
  * [50] Ce Zheng, Lei Li, Qingxiu Dong, Yuxuan Fan, Zhiyong Wu, Jingjing Xu, and Baobao Chang.  Can we edit factual knowledge by in-context learning?  ArXiv, abs/2305.12740, 2023.
  * [51] Zexuan Zhong, Zhengxuan Wu, Christopher D Manning, Christopher Potts, and Danqi Chen.  Mquake: Assessing knowledge editing in language models via multi-hop questions.  arXiv preprint arXiv:2305.14795, 2023.
  * [52] Chen Zhu, Ankit Singh Rawat, Manzil Zaheer, Srinadh Bhojanapalli, Daliang Li, Felix X. Yu, and Sanjiv Kumar.  Modifying memories in transformer models.  ArXiv, abs/2012.00363, 2020.

##  Appendix A Details of Prompts

[Demo]
---
Question: $(U.S.,president\ is,\text{<mask>})$, what is the answer for <mask>?
Answer: Joe Biden.
[Instruction]
Please refer to the above demo and complete the following task:
[Task]
$(o_{z_{m}},r_{b_{m+1}},\text{<mask>})$, what is the answer for <mask>?
Table 2: Prompt $\text{P}_{\text{forward}}$ used to determine the next value
along the chain in Equation 8. [Demo]  include several high-quality
demonstrations handwritten by humans. $o_{z_{m}}$ and $r_{b_{m+1}}$ are the
inputs for the prompt template. [Demo]
---
Question: $(\text{<mask>},president\ is,Joe\ Biden)$, what is the answer for
<mask>?
Answer: United states.
[Instruction]
Please refer to the above demo and complete the following task:
[Task]
$(\text{<mask>},r_{b_{j}},o_{z_{j}})$, what is the answer for <mask>?
Table 3: Prompts $\text{P}_{\text{back}}$ used to determine the previous value
along the chain in Equation 9. $r_{b_{j}}$ and $o_{z_{j}}$ are thes input for
prompt template.

##  Appendix B Retrieval for Forward Tracking and Back Tracking

In this section, we introduce the process of retrieving the edit memory for
forward tracking and back tracking. For each edit $e\in\mathcal{M}$, we denote
$e[s]$, $e[r]$ and $e[o^{*}]$ as subject, relation and object of edit $e$
respectively.

In the process of forward tracking, we need to whether there is edit $e$ in
$\mathcal{M}$, which $e[s]=o_{z_{m}}$ and $e[r]$ match with $r_{b_{m+1}}$.
Inspired by previous work [4], we introduce a two-step retrieval method: (i)
First, filter out all edits whose subject is not identical to $o_{z_{m}}$. ii)
Use dense retrieval to compare the semantic similarity between the relation of
the remaining edits and $r_{b_{m+1}}$, then select the most similar one.

Step 1: Filtering. This step extracts a subset $\mathcal{M}_{sub}$ from
$\mathcal{M}$ by selecting only the edits that fulfill the subject constraint.
Formally, this is represented as:

$\mathcal{M}_{sub}=\\{e\in\mathcal{M}\mid e[s]\in\\{o_{z_{m}}\\}\cup
Alias(o_{z_{m}})\\}$ (11)

where Alias represent multiple different alias of the entities captured from
Wikidata via entity linking [22].

Step 2: Re-ranking. This step aims to compare the semantic similarity between
$e[r]$ and $r_{b_{m+1}}$. For this, we first encode $r_{b_{m+1}}$ using
encoder $E$, as follows:

$v_{r}=E(r_{b_{m+1}})$ (12)

Then, we re-rank edits in $\mathcal{M}_{sub}$ based on the cosine similarity
(sim) of the relation and select the edit exhibiting highest relational
similarity with the retrieved result.

$e^{*},\eta=\operatorname*{arg\,max}_{e\in\mathcal{M}_{sub}}\
{\text{sim}(E(e[r]),v_{r})},$ (13)

where $e^{*}$ is the retrieved edit, and $\eta$ is the corresponding
similarity compared against a threshold $\theta$, as follows: if
$\eta>\theta$, we assume the relevant edit is found, and $o_{z_{m+1}}$ is the
object of this edit, _i.e.,_ $o_{z_{m+1}}=e^{*}[o^{*}]$, otherwise we assume
the relevant edit is not found.

Similar to forward tracking, the objective of back tracking is to obtain
$o_{z_{j-1}}$ based on $o_{z_{j}}$ and $r_{b_{j}}$. We first extract subset
$\mathcal{M}_{sub}$ to filter out all edits whose object is not identical to
$o_{z_{m}}$. Then we match the edits in $\mathcal{M}_{sub}$ according to the
semantic similarity between its relation and $r_{b_{j}}$ and select the edit
$e^{*}$ with the highest similarity $\eta$ compared against a threshold
$\theta$, as follows: if $\eta>\theta$, we assume the edit is found, _i.e.,_
$o_{z_{j-1}}=e^{*}[s]$, otherwise we assume the relevant edit is not found.

##  Appendix C Data Construction of RKe-eval

RKe-eval is created using Wikidata
111https://www.wikidata.org/wiki/Wikidata:Main_Page, a large-scale knowledge
base encompassing millions of real-world entities and their associated
knowledge triplets. We explain the data curation process as follows:

Step 1: Collecting high-quality logic rules and relation templates. We first
employ the rule-mining tools to discover a larger number of rules from
Wikidata, later manually select a small subset of representative rules. Table
8 illustrated multiple different rules used for the curation of RKe-eval.
Following prior work [51], we also collect some common relations from Wikidata
and create a question template and cloze-style statement template for them, as
shown in Table 7.

Step 2: Constructing relation path template. Multi-hop questions require a
series of reasoning steps to come up with the final answer. We refer to all
the relations involved in this process as a relation path template, _e.g.,_
for the question: "What is the nationality of the owner of company of Tom?",
the corresponding relation path template is "company_is($z_{0}$,$z_{1}$),
owner_is($z_{1}$,$z_{2}$), nationality($z_{2}$,$z_{3}$)". Once given with the
start point $z_{0}$, we can get a potentially valid multi-hop question. We get
the potential relation path template by arranging all the relation templates
obtained in the previous step, and delete inappropriate templates, _e.g.,_
"_company $\\_$is($z_{0}$,$z_{1}$),
educated$\\_$at$\\_$university($z_{1}$,$z_{2}$)_" is an inappropriate template
since a company is not a person.

Step 3: Generating knowledge paths. Then we use the above relation path
template to generate a knowledge path by setting the start point $z_{0}$ for a
specific entity. This is an iterative process which involves determining the
specific object $o$ based on the $r(s,?)$, with the subject $s$ and relation
$r$ as known. Following the previous work [4], we use the database language
SPASQL to query the object $o$ for each iterative process.

Step 4: Introducing counterfactual edit to the knowledge path. Next, we use
the counterfactual edit to modify some reasoning steps of the knowledge path
to mimic the knowledge editing scenario in reality.

Step 5: Using rules to curate multi-hop questions. We finally combine some
connected relations in the knowledge path into one relation based on logic
rules, _e.g.,_ Combine "_father $\\_$is(Tom, John), wife$\\_$is(John, Amy),
company_is(Amy, Twitter)_" into "_mother $\\_$is(Tom, Amy), company_is(Amy,
Twitter)_". In this way, we can construct a challenging multi-hop question
that can be used to evaluate the ability of end-models to maintain knowledge
consistency of KE methods. Finally, we use GPT-4 to transform them into
natural language forms.

Question | Who is the father of the first lady of America?
---|---
Edit |  head_of_state(America, Joe Biden $\rightarrow$ Albert Einstein)
Rule |  head_of_state $\land$ wife_is $\rightarrow$ first_lady_is
Reasoning |  head_of_state (America, Albert Einstein) $\land$ wife_is (Albert Einstein, Elsa Einstein)
|  $\rightarrow$ first_lady_is (America, Elsa Einstein)
Inference Chain | first_lady_is (America, Elsa Einstein)
| father_is (Elsa Einstein, Rudolf Einstein)
Answer | Rudolf Einstein

Table 4: An example illustration of Left-Edit on RKe-eval. It shows how Rule-
Ke employed logic rules to infer derived knowledge, helpful for the model to
generate the correct answer.

##  Appendix D Additional Experimental Details

###  D.1 Dataset

(i) MQuAKE-CF-3K [51] is a knowledge editing dataset, which contains a number
of k-hop questions ($k\in\\{2,3,4\\}$) questions, each k-hop question is
associated with at least one counterfactual edit. The statistics of MQuAKE-
CF-3K are shown in Table 5.
(ii) RKe-eval is a dataset proposed by us to evaluate the ability of knowledge
editing methods to maintain knowledge consistency. Like MQuAKE, RKe-eval
contains a number of multi-hop questions related to one or more edits. The
Statistics of RKe-eval are shown in Table 6.

#Edits | 2-hop | 3-hop | 4-hop | Total
---|---|---|---|---
1 | 513 | 356 | 224 | 1093
2 | 487 | 334 | 246 | 1067
3 | - | 310 | 262 | 572
4 | - | - | 268 | 268
All | 1000 | 1000 | 1000 | 3000

Table 5: Statistics of MQuAKE-CF-3K.

Situation | 2-hop | 3-hop | 4-hop | Total
---|---|---|---|---
Left-Edit | 330 | 410 | 342 | 1082
Right-Edit | 357 | 290 | 244 | 891
Both-Edit | 244 | 156 | 209 | 609
No-Edit | - | 153 | 212 | 365
All | 931 | 1009 | 1007 | 2947

Table 6: Statistics of RKe-eval.

###  D.2 Large Models

We conduct experiments on the following base language models: (i) LLaMa-2-7B
[37] is a very powerful open source pre-trained large language model, and we
use the implementation of huggingface [43]. (ii) LLaMa-2-7B-chat [37] is fine-
tuned version of LLaMa-2-7B with stronger ability in chat. (iii)
GPT-3.5-turbo-instruct [31] is a variant of the most capable GPT-3.5 series
model, specifically designed to follow instructions and complete tasks
thoughtfully.

###  D.3 Baseline Methods

Parameter-based editing method. We take three parameter-based editing methods
as baselines.

  1. 1.

Fine-tuning (FT) [52] simply perform a gradient descent algorithm on the model
based on the new knowledge to update the parameters.

  2. 2.

ROME [28] first locates factual knowledge at a specific layer of the
transformer architecture and then updates the feedforward network of this
layer to insert new knowledge.

  3. 3.

MEMIT [29] modifies a range of layer feedforward networks and expands ROME to
modify a large amount of knowledge.

Memory-based editing method. We evaluate the following state-of-the-art
memory-based editing methods.

  1. 1.

MeLLo [51] uses the plan-and-solve paradigm. When solving a sub-problem, MeLLo
first asks the model to generate a candidate answer and then gives the
retrieved edits to the model to determine whether they are relevant.

  2. 2.

PokeMQA [6] extend the MeLLo, adopt a two-stage retrieval, and decouple the
responsibilities of LLM.

  3. 3.

TEMPLE-MQA [4] adopts a structural retrieval method, effectively enhancing the
accuracy of retrieving relevant edits while addressing the challenge of
temporal editing.

###  D.4 Evaluation Metric

Multi-hop Accuracy (Acc) is used to evaluate the performance of the model in
multi-hop question-answering. If the answer generated by a model is equal to
the target answer ($a^{*}$) or its alias ($Alias(a^{*})$), we consider it as a
correct answer. Assume that the edited model is expressed as $f^{*}(\cdot)$,
the multi-hop accuracy is computed as follows:

$\mathbbm{1}\left[f^{*}(q)\in\\{a^{*}\\}\cup Alias(a^{*})\right].$ (14)

What needs to be emphasized is that each instance in MQuAKE-CF-3K contains
three multi-hop questions, and as long as the model can correctly answer one
of them, the instance is considered correct. This can be represented by the
following formula:

$\mathbbm{1}\left[\bigvee_{q\in\mathcal{Q}}[f^{*}(q)\in\\{a^{*}\\}\cup
Alias(a^{*})\right].$ (15)

Where $\mathcal{Q}$ represent the multi-hop questions for each instance.

Relation | Question template | Cloze-style statement template
---|---|---
the_First_Lady_is | Who is the First Lady of [S]? | The First Lady of [S] is
head_of_state_is | Who is the current head of state in [S]? | The current head of state in [S] is
wife_is | Who is [S]’s wife? | [S]’s wife is
live_in_the_country | Which country does [S] live in? | [S] live in the country of
live_in_the_place | Where does [S] live in? | [S] live in
located_in_the_country | Which country is [S] located in? | [S] located in the country of
studying_in_the_country | Which country is [S] studying in? | [S] study in the country of
educated_at_the_university | Which university is [S] educated at? | The university where [S] is educated is
native_language_is | What is [S]’s native language? | [S]’s countryis
holds_nationality_in | What is [S]’s nationality? | [S]’s nationality is
official_language_is | What is the official language of [S]? | The official language of [S] is
father_is | Who is [S]’s father? | [S]’s father is
mother_is | Who is [S]’s mother? | [S]’s mother is
husband_is | Who is [S]’s husband? | [S]’s husband is
uncle_is | Who is [S]’s uncle? | [S]’s uncle is
parent_is | Who is [S]’s parent? | [S]’s parent is
brother_is | Who is [S]’s brother? | [S]’s brother is
aunt_is | Who is [S]’s aunt? | [S]’s aunt is
sister_is | Who is [S]’s sister? | [S]’s sister is
grandmother_is | Who is [S]’s grandmother? | [S]’s grandmother is
grandfather_is | Who is [S]’s grandfather? | [S]’s grandfather is
nephew_is | Who is [S]’s nephew? | [S]’s nephew is
sibling_is | Who is [S]’s sibling? | [S]’s sibling is
son_is | Who is [S]’s son? | [S]’s son is
niece_is | Who is [S]’s niece? | [S]’s niece is
daughter_is | Who is [S]’s daughter? | [S]’s daughter is
mother-in-law_is | Who is [S]’s mother-in-law? | [S]’s mother-in-law is
spouse_is | Who is [S]’s spouse? | [S]’s spouse is
father-in-law_is | Who is [S]’s father-in-law? | [S]’s father-in-law is
born_in_the_place | Where is [S]’s birthplace? | [S]’s birthplace is
party_membership_is | What is [S]’s party membership? | [S]’s party membership is
is_a_political_party | Which country is [S] a political party in? | [S] is a political party of
located_in_the_continent | Which continent is [S] located in? | [S] located in the continent of
located_in_the_continent | Which continent is [S] a country in? | [S] is a country of
located_in_the_country | Which country is [S] a university in? | [S] is a university of
capital_is | What is the capital of [S]? | The capital of [S] is
affiliated_with_the_religion | Which religion is [S] affiliated with? | [S] is affiliated with the religion of
occupation_is | What is [S]’s occupation? | [S]’s occupation is
died_in_the_place | Where is [S]’s place of death? | [S] died in
workplace_is_at | Where is [S]’s workplace? | [S]’s workplace is at

Table 7: Question templates and cloze-style statement templates used in RKe-
eval father_is($z_{0}$,$z_{1}$) $\wedge$ wife_is($z_{1}$,$z_{2}$)
$\rightarrow$ mother_is($z_{0}$,$z_{2}$)
---
parent_is($z_{0}$,$z_{1}$) $\wedge$ sister_is($z_{1}$,$z_{2}$) $\rightarrow$
aunt_is($z_{0}$,$z_{2}$)
sibling_is($z_{0}$,$z_{1}$) $\wedge$ son_is($z_{1}$,$z_{2}$) $\rightarrow$
nephew_is($z_{0}$,$z_{2}$)
parent_is($z_{0}$,$z_{1}$) $\wedge$ brother_is($z_{1}$,$z_{2}$) $\rightarrow$
uncle_is($z_{0}$,$z_{2}$)
mother_is($z_{0}$,$z_{1}$) $\wedge$ husband_is($z_{1}$,$z_{2}$) $\rightarrow$
father_is($z_{0}$,$z_{2}$)
sibling_is($z_{0}$,$z_{1}$) $\wedge$ daughter_is($z_{1}$,$z_{2}$)
$\rightarrow$ niece_is($z_{0}$,$z_{2}$)
parent_is($z_{0}$,$z_{1}$) $\wedge$ mother_is($z_{1}$,$z_{2}$) $\rightarrow$
grandmother_is($z_{0}$,$z_{2}$)
parent_is($z_{0}$,$z_{1}$) $\wedge$ father_is($z_{1}$,$z_{2}$) $\rightarrow$
grandfather_is($z_{0}$,$z_{2}$)
spouse_is($z_{0}$,$z_{1}$) $\wedge$ mother_is($z_{1}$,$z_{2}$) $\rightarrow$
mother-in-law_is($z_{0}$,$z_{2}$)
spouse_is($z_{0}$,$z_{1}$) $\wedge$ father_is($z_{1}$,$z_{2}$) $\rightarrow$
father-in-law_is($z_{0}$,$z_{2}$)
head_of_state_is($z_{0}$,$z_{1}$) $\wedge$ wife_is($z_{1}$,$z_{2}$)
$\rightarrow$ the_First_Lady_is($z_{0}$,$z_{2}$)
holds_nationality_in($z_{0}$,$z_{1}$) $\wedge$
official_language_is($z_{1}$,$z_{2}$) $\rightarrow$
native_language_is($z_{0}$,$z_{2}$)
party_membership_is($z_{0}$,$z_{1}$) $\wedge$
is_a_political_party($z_{1}$,$z_{2}$) $\rightarrow$
holds_nationality_in($z_{0}$,$z_{2}$)
live_in_the_place($z_{0}$,$z_{1}$) $\wedge$
located_in_the_country($z_{1}$,$z_{2}$) $\rightarrow$
live_in_the_country($z_{0}$,$z_{2}$)
born_in_the_place($z_{0}$,$z_{1}$) $\wedge$
located_in_the_country($z_{1}$,$z_{2}$) $\rightarrow$
holds_nationality_in($z_{0}$,$z_{2}$)
located_in_the_country($z_{0}$,$z_{1}$) $\wedge$
located_in_the_continent($z_{1}$,$z_{2}$) $\rightarrow$
located_in_the_continent($z_{0}$,$z_{2}$)
educated_at_the_university($z_{0}$,$z_{1}$) $\wedge$
located_in_the_country($z_{1}$,$z_{2}$) $\rightarrow$
studying_in_the_country($z_{0}$,$z_{2}$)
Table 8: Logic rules in RKe-eval.

##  Appendix E Limitations

While large language models (LLMs) have garnered widespread attention due to
their exceptional knowledge comprehension capabilities, research shows they
experience hallucinations and may generate incorrect knowledge. While Rule-Ke
is an attempt to overcome this limitation, yet employing our model may not
completely eradicate this problem. This challenge stems from: (i) inherent
limitations underlying LLMs modeling assumptions, (ii) in-consistency in the
data used for training the large models, however, these problems could be
alleviated as the data and capabilities of LLMs continue to improve in the
future.

Besides, although Large Language Models (LLMs) have garnered widespread
attention for their remarkable capacity for knowledge comprehension [48, 47,
4, 1, 49], enabling tailored solutions across various applications, they also
face critical issues such as privacy concerns [11], and explainability [13,
23, 12]. LLM applications typically involve data containing sensitive
information, necessitating effective solutions to safeguard privacy [46]. One
promising approach to address this challenge is the design of Differentially
Private (DP) algorithms [5]. DP offers provable protection against
identification and is resilient to arbitrary auxiliary information that may be
available to attackers. While there have been numerous studies on DP machine
learning [14, 39, 40, 35, 15] and DP deep learning [44, 45], most of these
efforts have primarily focused on either continuous tabular data or image
data. Unfortunately, less attention has been given to adapting variants of DP
algorithms to the context of Natural Language Processing (NLP) and the text
domain. Addressing this gap is crucial as text data presents its own unique
challenges and characteristics that necessitate specialized privacy-preserving
techniques. By developing and refining DP algorithms tailored to NLP tasks, we
can enhance the privacy protections of LLMs and enable their responsible and
ethical deployment across various domains. We will leave it for future work.


# Self-organization of oscillation in an epidemic model for COVID-19

Takashi Odagaki∗

Kyushu University
Nishiku, Fukuoka 819-0395, Japan
and
Research Institute for Science Education, Inc.
Kitaku, Kyoto 603-8346, Japan
∗Corresondence to: Research Institute for Science Education, Inc.,
Kitaku, Kyoto 603-8346, Japan
Email address<EMAIL_ADDRESS>

###### Abstract

On the basis of a compartment model, the epidemic curve is investigated when
the net rate $\lambda$ of change of the number of infected individuals $I$ is
given by an ellipse in the $\lambda$-$I$ plane which is supported in
$[I_{\ell},I_{h}]$. With $a\equiv(I_{h}-I_{\ell})/(I_{h}+I_{\ell})$, it is
shown that (1) when $a<1$ or $I_{\ell}>0$, oscillation of the infection curve
is self-organized and the period of the oscillation is in proportion to the
ratio of the difference $(I_{h}-I_{\ell})$ and the geometric mean
$\sqrt{I_{h}I_{\ell}}$ of $I_{h}$ and $I_{\ell}$, (2) when $a=1$, the
infection curve shows a critical behavior where it decays obeying a power law
function with exponent $-2$ in the long time limit after a peak, and (3) when
$a>1$, the infection curve decays exponentially in the long time limit after a
peak. The present result indicates that the pandemic can be controlled by a
measure which makes $I_{\ell}<0$.

##  1 Introduction

Since the first outbreak in China in November 2019, COVID-19 has been
spreading in all continents including Antarctica. According to a recent
analysis of infection status of 186 countries [1, 2], the time dependence of
the daily confirmed new cases in more than 80 countries show oscillations
whose periods range from one to five months depending on the country. The
period of the oscillation is much shorter than that of Spanish flu in
1918$\sim$1919 which is the result of the mutation of virus, and it is an open
question why the infection curve of COVID-19 shows oscillation in some
countries.

There have been several compartmental models which explain epidemic
oscillations [3, 4, 5]. The simplest idea to explain the oscillation is to
introduce a sinusoidal time dependence of parameters of the model. Recently,
Greer et al [6] introduced a dynamical model with time-varying births and
deaths which shows oscillations of epidemics.

Since the infection curve of COVID-19 shows different features depending on
the country, the infection curve must have a strong relation to the government
policy, and the conventional approach may not be appropriate to COVID-19. In
fact, different measures have been employed in each country by its government
and citizens have been restricting the social contact among them, both of
which depend on the infection status. Therefore, parameters including
transmission coefficient of the virus can be considered to be a function of
the infection status, and the non-linear effects due to this dependence must
be clarified.

In this paper, I introduce a compartment model in which the net rate $\lambda$
of change of the number of infected individuals $I$ is a function of $I$ and
the function is given by an ellipse in the $\lambda$-$I$ plane which is
supported in $[I_{\ell},I_{h}]$. Here, $I_{h}$ is the upper limit of the
number of infected individuals above which the government does not allow, and
$I_{\ell}$ is the lowest value below which the government will lift measures.
I show that an oscillatory infection curve can be self-organized when
$I_{\ell}>0$ and that the period is determined by the ratio of the difference
$I_{h}-I_{\ell}$ and the geometric mean $\sqrt{I_{h}I_{\ell}}$ of $I_{h}$ and
$I_{\ell}$. I also show that when $I_{\ell}=0$ the infection curve in the long
time limit after a single peak decays following a power law function with
exponent -2 and when $I_{\ell}<0$ it decays exponentially in the long time
limit.

##  2 Model country

In most of compartmental models for epidemics, the number of infected
individuals $I(t)$ is assumed to obey

$\frac{dI(t)}{dt}=\lambda I(t).$ (1)

The net rate of change $\lambda$ of the number of infected individuals is
written generally as

$\lambda=\beta\frac{S}{N}-\gamma-\alpha.$ (2)

Here, $\beta$ and $\gamma$ are the transmission rate of virus from an infected
individual to a susceptible individual and a per capta rate for becoming a
recovered non-infectious (including dead) individual (R), respectively, and
$S$ and $N$ are the number of susceptible individuals and the total
population. In Eq. (2), $\alpha$ is a model-dependent parameter representing
different effect of epidemics. In the SIR model [8], it is assumed that no
effects other than transmission and recovery are considered and thus
$\alpha=0$ is assumed. The SEIR model [9] introduces a compartment of exposed
individuals (E), and if one sets $\alpha=(dE/dt)/I$, the basic equation of the
SEIR model reduces to Eq. (1).

The SIQR model [10, 11] separates quarantined patients (Q) as a compartment in
the population and $\alpha$ in Eq. (1) is given by the quarantine rate
$q\equiv\Delta Q(t)/I(t)$ where $\Delta Q(t)$ is the daily confirmed new cases
[7]. In the application of the SIQR model to COVID-19, it has been shown that

$\Delta Q(t)\propto I(t-\tau),$ (3)

where $\tau$ is a typical value of the waiting time between the infection and
quarantine of an infected individual. Therefore, the number of the daily
confirmed new cases can be assumed to obey Eq. (1) with the redefined time
$t-\tau$. Since $\Delta Q(t)$ is treated as an explicit variable instead of
$I(t)$, the SIQR model is relevant to COVID-19.

In this paper, I focus on the time evolution of $I(t)$ governed by Eq. (1) for
COVID-19. The transmission coefficient is determined by characteristics of the
virus and by government policies for lockdown measure and vaccination and by
people’s attitude for social distancing. Medical treatment of infected
individuals affects $\gamma$ and the government policy on PCR test changes the
quarantine rate. The government policies are determined according to the
infection status and therefore the rate of change is considered to be a
function of $I(t)$ in Eq. (1).

Here, I consider a model country in which $\lambda$ depends on $I$ through

$\left(\frac{\lambda}{\lambda_{0}}\right)^{2}+\left(\frac{I-I_{0}}{\Delta}\right)^{2}=1.$
(4)

This implies that when $I$ becomes large, some policies are employed to reduce
$\lambda$ to the negative area so that $I(t)$ begins to decline and when $I$
becomes small enough, then some measures are lifted and $\lambda$ becomes
positive again. In fact, the plots of $\lambda(t)$ against $I(t)$ in many
countries show similar loops [2]. Note that $\lambda=0$ corresponds to either
a maximum or a minimum of the number of infected individuals.

Figure 1 shows this dependence, namely $I_{h}\equiv I_{0}+\Delta$ and
$I_{\ell}\equiv I_{0}-\Delta$ are the maximum and minimum of the number of
infected individuals set by the policy in the country. When $I_{\ell}<0$,
$\lambda$ in the region $I<0$ is not relevant since no infected individuals
exist in this region.

Figure 1:  The dependence of the net rate $\lambda$ on the number of infected
individuals $I$ in a model country.

##  3  Infection curve and self-organization of oscillation

In order to solve Eq. (1) with Eq. (4), I introduce a variable $x$ through

$\displaystyle\lambda$ $\displaystyle=$ $\displaystyle\lambda_{0}\cos x,$ (5)
$\displaystyle I-I_{0}$ $\displaystyle=$ $\displaystyle\Delta\sin x$ (6)

and rewrite Eq. (1) as

$a\frac{dx}{d\tilde{t}}=1+a\sin x,$ (7)

where $\tilde{t}\equiv\lambda_{0}t$ is the time scaled by $\lambda_{0}^{-1}$
and $a\equiv\Delta/I_{0}\geq 0$ is a parameter of the model. Equation (7) can
be solved readily under the initial condition $I(t=0)=I_{0}$:

$\tilde{t}=\left\\{\begin{array}[]{ll}\frac{\displaystyle
2a}{\displaystyle\sqrt{1-a^{2}}}\left[\arctan\frac{\displaystyle\tan(x/2)+a}{\displaystyle\sqrt{1-a^{2}}}-\arctan\frac{\displaystyle
a}{\displaystyle\sqrt{1-a^{2}}}\right]&\quad\mbox{when $a<1$},\\\
\frac{\displaystyle 2\tan(x/2)}{\displaystyle 1+\tan(x/2)}&\quad\mbox{when
$a=1$},\\\ \frac{\displaystyle
a}{\displaystyle\sqrt{a^{2}-1}}\left[\ln\frac{\displaystyle\tan(x/2)+a-\sqrt{a^{2}-1}}{\displaystyle\tan(x/2)+a+\sqrt{a^{2}-1}}-\ln\frac{\displaystyle
a-\sqrt{a^{2}-1}}{\displaystyle a+\sqrt{a^{2}-1}}\right]&\quad\mbox{when
$a>1$}.\end{array}\right.$

The infection curve is given in terms of $\tan(x/2)$ by

$\frac{I(t)}{I_{0}}=1+\frac{a\tan(x/2)}{1+\tan^{2}(x/2)}.$ (8)

The infection curves are shown for $a=0.4,0.6,0.8,1$ in Fig. 2(a) and for
$a=1,2,4,6$ in Fig. 2(b). Therefore, the infection curve is a periodic
function when $a<1$ and a decaying function with a single peak when $a\geq 1$.

(a) (b)

Figure 2:  The infection curve for the model country. (a) When $a<1$, a wavy
infection curve is self-organized. (b) When $a>1$ the infection curve is a
decaying function with a single peak. The infection curve for $a=1$ shown in
both panels obeys a power-law decay in the long time limit after a peak.

Characteristics of the infection curve are in order:
(1) When $a<1$, the infection curve shows a self-organized oscillation which
can be characterized as follows:

  1. 1.

The location of the peak $I_{\rm max}/I_{0}=1+a=I_{h}/I_{0}$ and the bottom
$I_{\rm min}/I_{0}=1-a=I_{\ell}/I_{0}$ are given by

$\displaystyle\tilde{t}_{\rm max}(n)$ $\displaystyle=$
$\displaystyle\frac{2a}{\sqrt{1-a^{2}}}\arctan\left[\sqrt{\frac{1-a}{1+a}}+(n-1)\pi\right],$
(9) $\displaystyle\tilde{t}_{\rm min}(n)$ $\displaystyle=$
$\displaystyle\frac{2a}{\sqrt{1-a^{2}}}\arctan\left[\sqrt{\frac{1+a}{1-a}}+(n-1)\pi\right],$
(10)

respectively, where $n=1,2,\dots$.

  2. 2.

Therefore, the period $T$ is given by

$T\lambda_{0}=\frac{2\pi
a}{\sqrt{1-a^{2}}}=\frac{4\pi(I_{h}-I_{\ell})}{\sqrt{I_{h}I_{\ell}}}.$ (11)

Namely, the period is given by the ratio of a half of the difference
$\Delta=\frac{I_{h}-I_{\ell}}{2}$ and the geometrical mean
$\sqrt{I_{h}I_{\ell}}$ of $I_{h}$ and $I_{\ell}$.

(2) When $a=1$, the infection curve shows a peak, after which it decays to
zero. It can be characterized as follows:

  1. 1.

The infection curve reaches its maximum $I_{\rm max}/I_{0}=2$ at
$t\lambda_{0}=1$.

  2. 2.

In the long time limit, it decays as $t^{-2}$.

(3) When $a>1$, the infection curve shows a peak, after which it decays to
zero. It can be characterized as follows:

  1. 1.

The infection curve reaches its maximum $I_{\rm max}/I_{0}=1+a$ at
$t\lambda_{0}=\frac{a}{\sqrt{a^{2}-1}}\ln(a+\sqrt{a^{2}-1})$.

  2. 2.

The infection curve returns to the initial state $I(t)=I_{0}$ at
$t\lambda_{0}=\frac{a}{\sqrt{a^{2}-1}}\ln\frac{a+\sqrt{a^{2}-1}}{a-\sqrt{a^{2}-1}}$.

  3. 3.

In the long time limit, the effective relaxation time defined by
$\tau\equiv-\left(\frac{d\ln I}{dt}\right)^{-1}$ is given by
$\tau\lambda_{0}=\frac{a}{\sqrt{a^{2}-1}}$.

Figure 3 shows the period for $a<1$ and the relaxation time for $a>1$ as
functions of $a$.

Figure 3:  The period when $a<1$ and the relaxation time in the long time
behavior when $a>1$ are shown as functions of $a$.

##  4 Discussion

I have shown that oscillation of the infection curve can be self-organized in
the epidemic model described by an ordinary differential equation which
exploits the net rate of change Eq. (4) depending on the number of infected
individuals. All countries employ their own policy which depends on the
infection status of the country and the relation Eq. (4) represents general
trend of the policy. Namely, when the number of infected individuals
approaches the maximum number acceptable in a country, a strong measure is
introduced to make the net rate of change $\lambda$ negative, and the measure
will be lifted when the number of infected individuals is considered to be
small enough, which makes $\lambda>0$. Therefore, the policy with $I_{\ell}>0$
itself is considered to be the origin of the oscillation of the infection
curve and the policy with $I_{\ell}<0$ seems to have succeeded in controlling
the pandemic [2]. As an example, I show in Fig. 4(a) the time dependence of
daily confirmed new cases in Japan from April 5, 2020 to February 11, 2021
which consists of three waves. Using $\lambda$ determined by fitting the data
by piece-wise quadratic functions as shown by the solid curve [2], I show the
correlation between $\lambda$ and $\Delta Q$ in Fig. 4(b).

(a) (b)

Figure 4:  (a) The time dependence of daily confirmed new cases in Japan from
April 5, 2020 to February 11, 2021. The dependence is fitted by piece-wise
quadratic functions. (b) The net rate is shown as a function of the number of
new cases. The spiral nature of this plot indicates an enhancing wavy behavior
of the infection curve. The jumps seen in the plot are due to the procedure
which does not impose the continuity of the curvature.

Some of oscillations in biological systems such as the prey and predator
system have been explained by the Lotka-Volterra model [12, 13], which is
essentially a coupled logistic equation and it is reducible to a second order
non-linear differential equation for one variable. Since the present model is
based on a first order non-linear differential equation, the origin of
oscillatory solution of the present model is different from that of the Lotka-
Volterra model.

Several important implications of the present results are:
(1) In order to control the outbreak, a policy is needed to make $a>1$ or
$I_{\ell}<0$ and $\lambda<0$. Since $\lambda$ is determined by $\beta$, $S$,
$\gamma$ and $\alpha$(or $q$), this can be achieved by the lockdown measure to
reduce $\beta$, by the vaccination to reducing $S$ and by the quarantine
measure to increase $q$.
(2) The worst policy is $I_{\ell}>0$. In this case, oscillation continues
until $\lambda$ becomes negative due to the herd immunity by vaccination
and/or infection of a significant fraction of the population.
(3) In order to make $\lambda$ negative, it has been rigorously shown that
increasing the quarantine rate $q$ is more efficient than reducing the
transmission coefficient $\beta$ by the lockdown measure [14].
This result indicates that the pandemic can be controlled only by keeping
measures of $\lambda<0$ till $I=0$.
(4) It should be remarked that the change in the infectivity of the virus due
to mutation can be included in $\lambda(I)$ in the present model. Namely
effects due to new variants of SARS-CoV-2 found in UK, in South Africa or in
Brazil can be included by moving the state to a new $\lambda$ vs $I$ relation.

In this study, I assumed that $I_{0}$ is fixed and the dependence of $\lambda$
on $I$ is symmetric. It is easy to generalize the present formalism to the
case of non-symmetric dependence of $\lambda$ on $I$.

Acknowledgments
This work was supported in part by JSPS KAKENHI Grant Number 18K03573.

## References

  * [1] Coronavirus Resource Center, Johns Hopkins University
https://coronavirus.jhu.edu/

  * [2] T. Odagaki and R. Suda, https://doi.org/10.1101/2020.12.17.20248445
  * [3] H. W. Hethcote, SIAM Rev. 42, 599-653 (2000).
http://doi:10.1137/S0036144500371907

  * [4] D. J. D. Earn, Mathematical epidemiology. Lecture Notes in Mathematics, vol. 1945 (eds. F. Brauer, P. van den Driessche, and J. Wu) 3-17 (Springer, Berlin, Germany, 2008).
https://doi.org/10.1007/978-3-540-78911-6

  * [5] X. Zhang, C. Shan, Z. Jin and H. Zhu, J. Differ. Equ. 266, 803-832 (2019).
https://doi:10.1016/j.jde.2018.07.054

  * [6] M. Greer, R. Saha, A.Gogliettino, C. Yu and K. Zollo-Venecek. R. Soc. open sci. 7, 191187 (2020).
https://dx.doi.org/10.1098/rsos.191187

  * [7] T. Odagaki, Sci. Rep. 11, 1936 (2021).
https://doi.org/10.1038/s41598-021-81521-z

  * [8] W. O. Kermack and A. G. McKendrick, Proc. Roy. Soc. A 115, 700-721 (1927).
https://doi.org/10.1098/rspa.1932.0171

  * [9] R. M. Anderson and R. M. May, Science 215, 1053-1060 (1982).
DOI: 10.1126/science.7063839

  * [10] H. Hethcote, M. Zhien and L. Shengbing, Math. Biosciences 180, 141-160 (2002).
https://doi.org/10.1016/S0025-5564(02)00111-6

  * [11] T. Odagaki, Infect. Dis. Model. 5, 691-698 (2020).
https://doi:10.1016/j.idm.2020.08.013

  * [12] A. J. Lotka, Proc. Natl. Acad. Sci. 6, 410-415 (1920).
https://doi.org/10.1073/pnas.6.7.410

  * [13] V. Volterra, Proc. Edin. Math. Soc. 6, 4-10 (1939).
https://doi.org/10.1017/S0013091500008476

  * [14] T. Odagaki, Physica A564, 125564–1-9 (2021).
https://doi.org/10.1016/j.physa.2020.125564