# Large Scale Knowledge Washing

Yu Wang1, Ruihan Wu1, Zexue He1, Xiusi Chen2, Julian McAuley1
1UC San Diego, 2UC Los Angeles
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Large language models show impressive abilities in memorizing world knowledge,
which leads to concerns regarding memorization of private information, toxic
or sensitive knowledge, and copyrighted content. We introduce the problem of
Large Scale Knowledge Washing, focusing on unlearning an extensive amount of
factual knowledge. Previous unlearning methods usually define the reverse loss
and update the model via backpropagation, which may affect the model’s fluency
and reasoning ability or even destroy the model due to extensive training with
the reverse loss. Existing works introduce additional data from downstream
tasks to prevent the model from losing capabilities, which requires downstream
task awareness. Controlling the tradeoff of unlearning and maintaining
existing capabilities is also challenging. To this end, we propose LaW (Large
Scale Washing) to update the MLP layers in decoder-only large language models
to perform knowledge washing, as inspired by model editing methods and based
on the hypothesis that knowledge and reasoning are disentanglable. We derive a
new objective with the knowledge to be unlearned to update the weights of
certain MLP layers. Experimental results demonstrate the effectiveness of LaW
in forgetting target knowledge while maintaining reasoning ability. The code
will be open-sourced at https://github.com/wangyu-ustc/LargeScaleWashing.

##  1 Introduction

Large Language Models (LLMs) are shown to memorize extensive knowledge or
factual relations (Chen et al., 2022; Alivanistos et al., 2022; Youssef et
al., 2023). However, the memorization of knowledge in LLMS raises both moral
and legal concerns. Factual knowledge may involve personal and sensitive
information whose memorization can violate strict regulations (Legislature,
2018; Act, 1996; Parliament and of the European Union, 2016), and memorizing
copyright content is also problematic – The New York Times111https://nytco-
assets.nytimes.com/2023/12/NYT_Complaint_Dec2023.pdf recently filed lawsuit
against OpenAI to protect its copyright of articles.

To prevent the undesired memorization of the above-mentioned knowledge, the
simplest solution is perhaps to label data that has the potential to raise
concerns in advance and exclude sensitive data from the pre-training stage.
However, this solution needs exhaustive human effort and may not be feasible
as the pretraining corpus for LLM is normally extremely large. This
impracticality motivates the study of machine _unlearning_ (Liu et al., 2024a;
Yao et al., 2024; Si et al., 2023; Yao et al., 2023b; Zhang et al., 2023).
When there are concerns about memorizing sensitive knowledge, these methods
aim to update the LLM to forget that knowledge with a relatively small
computational cost. Most of these methods are in the paradigm of defining an
“unlearning" loss (essentially the reverse loss of Next-Word-Prediction on the
unlearning dataset) and updating the full models by backpropagating from the
loss. However, updating the model with backpropagation may hurt the model’s
abilities in downstream tasks requiring reasoning. When the knowledge to be
unlearned scales up, it may require extensive updates of the model parameters,
which could even destroy the model (as shown in our experiments). Some efforts
to overcome this limitation define a “utility" loss from specific downstream
tasks and optimize both unlearning and utility losses (Liu et al., 2024a).
However, the applications of these methods may be limited when we focus on the
generalizability of LLMs where no downstream tasks are specified.

In this work, we focus on the Large Scale Knowledge Washing problem: how do we
unlearn the knowledge at scale (termed knowledge washing) from large language
models without affecting the model’s reasoning ability? (as shown in Figure 1)
We hypothesize that the knowledge and reasoning abilities in LLMs are
disentanglable, which gives rise to a feasible solution to the above problem.
To do so, we design a novel method named LaW (Large Scale Washing), which is
inspired by model editing methods (Meng et al., 2022, 2023), where MEMIT (Meng
et al., 2023) can perform massive knowledge editing by identifying a subset of
parameters in LLMs that account for the prediction of certain knowledge and
then editing these parameters with a closed-form equation. In the context of
knowledge washing, we follow this idea to first identify a subset of
parameters, and then derive a new objective to update the parameters. In the
knowledge-washing context, we can have a similar closed-form solution as in
the model-editing scenario. However, some important variables in this solution
are not available. This leads to our new objective, which requires
optimization rather than having a closed-form solution. Thus we introduce some
practical considerations to facilitate the optimization. The key difference
between LaW and model-editing ideas lies in the fact that model-editing
methods propose to _add_ factual relations in the model weights while LaW aims
to _delete_ factual relations.

We evaluate our methods using two small-scale datasets and a newly created
large-scale dataset derived from Wikipedia triplets, which includes 332,036
facts. Across different methods, we compare the accuracy and QA-F1 scores of
the generated answers from prompts formed from the triplets, demonstrating
that our approach achieves the most thorough knowledge washing. Importantly,
LaW maintains the model’s reasoning abilities, as verified by its performance
on various reasoning tasks.

Figure 1:  The diagram shows the process of Large Scale Knowledge Washing. We
aim to remove private, toxic or copyright knowledge such as SSN from the LLM,
while maintaining the model’s reasoning ability to answer questions such as
“$a>b,b>c,a?c$” whose answer should be “$>$”.

##  2 Related Work

##### Unlearning Knowledge in Large Language Model

Recent research has increasingly focused on the concept of machine unlearning
in the context of large language models (LLMs), highlighting both its
challenges and necessities (Liu et al., 2024a; Yao et al., 2024; Si et al.,
2023; Yao et al., 2023b; Zhang et al., 2023). Beyond addressing privacy
concerns necessitating unlearning in LLMs, several studies have employed
unlearning techniques to investigate the influence of specific subsets of
training data on model performance (Isonuma and Titov, 2024; Zhao et al.,
2024). To facilitate knowledge unlearning, various approaches have been
proposed. One method involves retraining the LLM on the targeted dataset using
a reverse loss function, coupled with training on an irrelevant dataset to
preserve performance on unrelated tasks. This can be implemented through the
addition of unlearning layers (Chen and Yang, 2023) or directly within the
large language model itself (Eldan and Russinovich, 2023). Unlike these
approaches, which apply to whole sequences in the unlearning subset, Wang et
al. (2024) suggest focusing on specific spans within sequences to minimize
disruption to unrelated tasks (Wang et al., 2024). Furthermore, an alternative
strategy known as in-context unlearning utilizes few-shot prompts to induce
forgetting of specific datasets directly within the context of use, presenting
a different approach from traditional training-based methods (Pawelczyk et
al., 2023). In a distinct line of research, other methods target the
mitigation of harmful outputs by collecting problematic prompts and applying
techniques such as instruction tuning (Liu et al., 2024b) or reinforced
learning (Lu et al., 2022) to prevent toxic responses.

##### Model Editing of LLMs

Model editing in large language models pertains to the modification of factual
relations within the models to integrate new world knowledge (Yao et al.,
2023a). Initial approaches to model editing focused on single-fact
adjustments, requiring the model to update one factual relation at a time.
Prominent methods in this domain include ROME (Meng et al., 2022), MEND
(Mitchell et al., 2022a), T-Patcher (Huang et al., 2023), and IKE (Zheng et
al., 2023). These techniques, however, often face stability issues after
multiple edits, complicating the process of batch editing, where multiple new
factual relations are introduced simultaneously. In response to these
challenges, advanced methods like GRACE (Hartvigsen et al., 2022) and SERAC
(Mitchell et al., 2022b) have been developed for effective batch editing.
Further advancements have tested these methodologies on larger models, such as
GPT2-XL and GPT-J-6B, with techniques like MEMIT (Meng et al., 2023) and
Model-Editing-FT (Gangadhar and Stratos, 2024). These approaches facilitate
the injection of multiple factual relations (up to the scale of around 10,000
factual relations) into the model and can be adapted for unlearning knowledge
in LLMs by altering factual statements to end-of-sequence tokens – for
example, changing "The mother tongue of David is French" to "The mother tongue
of David is <|endoftext|>" (here “<|endoftext|>” is the end-of-sequence token
in GPT-based models), effectively erasing specific information. While this
strategy offers a potential pathway for knowledge unlearning, it may not
surpass the effectiveness of our proposed method, which specifically focuses
on the removal rather than the addition of factual relations. This distinction
underscores the fundamental differences in approach between general model
editing techniques and our targeted strategy for knowledge unlearning.

##  3 Preliminary

###  3.1 The Structure of Decoder-only Large Language Models

Given the decoder-only language model $G$, the forward process is shown below:

$h_{t}^{l}=h_{t}^{l-1}(x)+\textrm{Attn}^{t}(h_{1}^{l-1},\cdots,h_{t}^{l-1})+W_{out}^{l}\sigma(W_{in}^{l}\gamma(h_{t}^{l})),$
(1)

where $L$ is the number of layers in $G$, $h_{t-1}^{l}$ represents the hidden
state of the $(t-1)$-th token at the $l$-th layer, with $W_{out}$ and $W_{in}$
being the weights in the MLP layers of the transformer. Here the attention and
MLP are expressed in parallel, as done in Meng et al. (2023) and Black et al.
(2021).

###  3.2 Previous Model Editing Strategy

As hypothesized and verified in Meng et al. (2022, 2023), the factual
knowledge is mostly stored in the MLP layers, which leads to their strategy of
updating the weight matrixes $W_{out}^{l}$ in Eq.(1). Meng et al. (2022) first
identifies the layer in the model that contributes most to the related
knowledge prediction, which we denote as $l_{0}$. Then the edit is performed
on the parameter $W_{out}^{l_{0}}$. For simplicity, we denote $W_{0}$ as the
specified parameter $W_{out}^{l_{0}}$ that needs to be updated. Inspired by
Geva et al. (2020), the linear layer $W_{0}$ can act as key-value memories,
associating input keys $K=\\{k_{i}\\}_{i=1}^{n}$ with corresponding values
$V=\\{v_{i}\\}_{i=1}^{n}$. The following equation shows the relationship
between $W_{0}$ and $K,V$:

$W_{0}=\arg\min_{W}\|WK-V\|_{F}^{2}\implies W_{0}=VK^{T}(KK^{T})^{-1}\implies
W_{0}KK^{T}=VK^{T},$ (2)

Then if we want to inject new factual relations, we first need identify the
new keys and values $K_{e}=\\{k_{j}\\}_{j=1}^{u}$ and
$V_{e}=\\{v_{j}\\}_{j=1}^{u}$ (here $K_{e}$ can be obtained via a forward pass
while $V_{e}$ needs to be calculated via gradient descent, the details are in
the paper Meng et al. (2022)), then the following equation is solved to obtain
the delta matrix $\Delta$:

$\Delta=\arg\min_{\hat{\Delta}}\parallel(W_{0}+\hat{\Delta})K_{1}-V_{1}\parallel_{F}^{2},$
(3)

where $\Delta$ is the desired update matrix that can be added onto $W_{0}$ to
obtain the new weight, $K_{1}$ and $V_{1}$ refer to the concatenation of
$K,K_{e}$ and $V,V_{e}$, respectively. This leads to the closed-form solution:

$\Delta=RK_{e}^{T}(KK^{T}+K_{e}K_{e}^{T})^{-1}$ (4)

where $R=V_{e}-W_{0}K_{e}$. Here although $K$ is hard to obtain as we do not
know how much knowledge is stored in the weight $W_{0}$, we can use abundant
text input to estimate $KK^{T}$. In ROME (Meng et al., 2022), single fact
editing is considered, where $K_{e}$ and $V_{e}$ are single column vectors,
and only one specific layer is edited. However, in MEMIT (Meng et al., 2023),
$K_{e}$ and $V_{e}$ are matrixes including all the new facts in the batch
editing procedure, where multiple sequential layers are edited to spread the
magnitude required to edit one layer into the successive layers to avoid
drastic parameter changes (Zhu et al., 2020). Instead of editing $l_{0}$
alone, MEMIT (Meng et al., 2023) proposes to edit the layer set denoted as
$\mathcal{R}=\\{l_{0}-|\mathcal{R}|+1,\cdots,l_{0}\\}$, where the necessary
adjustment to the weights $W^{l}$ in layer $l\in\mathcal{R}$ is given by:

$\Delta^{l}=R^{l}{K_{e}^{l}}^{T}(K^{l}{K^{l}}^{T}+K_{e}^{l}{K_{e}^{l}}^{T})^{-1},$

where $R^{l}=\frac{R^{l_{0}}}{l_{0}-l+1}$ and $R^{l_{0}}$ is the residual in
Eq.(4). These modifications are applied sequentially from the lower to the
upper layers, necessitating the recalculation of $K_{e}^{l}$ as edits
progress. The details of the above derivations are in Appendix A.

##  4 Problem Setup

We define the problem Large Scale Knowledge Washing as: How to wash a certain
large set of knowledge from the large language models without affecting the
model’s reasoning ability? Here by washing the knowledge, we refer to the
triplets that can be formed into single factual sentences. The knowledge set
can be defined as follows:

$\mathcal{E}_{w}=\\{(s_{i},r_{i},o_{i})\\}_{i=1}^{m},$ (5)

here $m$ is the total number of factual relations to be washed. Then for each
triplet, we convert it into a sentence to perform the washing. For instance,
the triplet (James Gobbo, residence, Toorak) is formed into a sentence James
Gobbo resides in Toorak. Then we have plenty of similar sentences as the
factual statements. After knowledge washing, we wish to obtain a model that
can only generate random answers or null answers when queried with the prompt
James Gobbo resides in. Meanwhile, we expect the model to still be able to
answer various reasoning questions without performance degradation. Note that
we do not have any new object to replace the triplet $o_{i}$ in
$(s_{i},r_{i},o_{i})$ in the washing process, while only the ground-truth
answer $o_{i}$ is accessible and washed. Differently, for model-editing
methods, there is a specific goal to edit the model to that leads to a simple
solution: edit all the triplets in $\mathcal{E}_{w}$ into $\mathcal{E}_{eos}$
defined as follows:

$\mathcal{E}_{eos}\triangleq\\{(s_{i},r_{i},\texttt{<|endoftext|>})\\}_{i=1}^{m},$
(6)

where <|endoftext|> is the end-of-sequence token in GPT-Style models.
Intuitively, a model’s capacity is finite, while Eq.(6) injects new factual
relations into the model which may disturb the model’s existing abilities. In
contrast, we propose to remove the knowledge from the model, which may lead to
less harm to the model’s reasoning abilities.

##  5 Methodology

As described in Section 3, the original model weight $W_{0}$ that requires
updating at layer $l_{0}$, can be expressed in terms of $K$ and $V$,
satisfying $W_{0}KK^{T}=VK^{T}$ (shown in Eq.(2)). In the context of model
editing, the keys for new knowledge $K_{e}$ are distinct from $K$. However,
when the goal is to erase specific knowledge, the relevant keys, denoted as
$K_{w}$, should be a subset of the original keys $K$. Here keys $K_{w}$ and
values $V_{w}$ represent all the memorized knowledge in Eq.(5). Unlike
incorporating new knowledge where $K_{1}$ is the concatenation of $K$ and
$K_{e}$, for knowledge erasure, $K_{2}$ comprises the remaining keys after
excluding $K_{w}$ from $K$. This adjustment modifies our objective to:

$\Delta=\arg\min_{\hat{\Delta}}\parallel(W_{0}+\hat{\Delta})K_{2}-V_{2}\parallel_{F}^{2},$
(7)

where $V_{2}$ corresponds to the values associated with $K_{2}$ within the
model weights. Although Eq.(7) provides a closed-form solution, obtaining
$V_{2}$ may be challenging, as it essentially represents the values that can
be used to derive $W_{0}$ during the pre-training phase. Theoretically, there
exist $K,V$ that can achieve the same $W_{0}$ as the pre-training, but
explicitly finding them is impractical. As $V_{2}$ is part of $V$, $V_{2}$ is
also hard to obtain. To circumvent this issue, we reformulate the problem as:

$\Delta=\arg\min_{\hat{\Delta}}\parallel(W_{0}+\hat{\Delta})K-V\parallel_{F}^{2}-\gamma\parallel(W_{0}+\hat{\Delta})K_{w}-V_{w}\parallel_{F}^{2},$
(8)

where $\gamma$ is a hyper-parameter balancing the trade-off between retaining
unrelated knowledge (and the model’s reasoning abilities) and erasing targeted
knowledge. We decompose the first term as:

$\displaystyle\min_{\hat{\Delta}}$
$\displaystyle\parallel(W_{0}+\hat{\Delta})K-V\parallel_{F}^{2}=\min\parallel\hat{\Delta}\parallel_{F}^{2}+2\textrm{tr}(\hat{\Delta}(W_{0}K-V)^{T})+||W_{0}K-V||_{F}^{2}$
$\displaystyle=\min_{\hat{\Delta}}\parallel\hat{\Delta}K\parallel_{F}^{2}+2\textrm{tr}(\hat{\Delta}KK^{T}W_{0}^{T})-2\textrm{tr}(\hat{\Delta}KV^{T})=\min_{\hat{\Delta}}\parallel\hat{\Delta}K\parallel_{F}^{2}$

where the last equality comes from the fact that $W_{0}=VK^{T}(KK^{T})^{-1}$
(see Eq.(2)). Although the exact $K$ is intractable, we estimate $KK^{T}$
using a large corpus as described in MEMIT (Meng et al., 2023). For the second
term in Eq.(8), as we also do not have the exact $V_{w}$, we choose to use
$W_{0}K_{w}$ as the approximation of $V_{w}$. This leads to the following
optimization problem:

$\Delta=\arg\min_{\hat{\Delta}}\parallel\hat{\Delta}K\parallel_{F}^{2}-\gamma\parallel\hat{\Delta}K_{w}\parallel_{F}^{2}$
(9)

This formulation aims to disrupt the outputs significantly for inputs $K_{w}$,
effectively "washing" the knowledge associated with $K_{w}$ from the model,
thereby preventing accurate predictions based on $V_{w}$.

This objective function serves as the basis for optimizing the search for an
optimal $\hat{\Delta}$, which, with a suitably tuned $\gamma$, allows for the
desired model edits. However, as the tradeoff between
$\parallel\hat{\Delta}K\parallel_{K}^{2}$ and
$\parallel\hat{\Delta}K_{w}\parallel$ might be hard to achieve, we propose to
reformulate the objective in Eq.(9) into:

$\Delta=\max_{\hat{\Delta}}\parallel\hat{\Delta}K_{w}\parallel_{F}^{2}\quad\textrm{s.t.}\frac{\parallel\hat{\Delta}K\parallel_{F}^{2}}{\parallel
K\parallel_{F}^{2}}\leq\beta$ (10)

Here $\beta$ is the hyperparameter used to control the tradeoff between the
reasoning ability (related to $\parallel\hat{\Delta}K\parallel_{F}^{2}$) and
the washing of previous knowledge (represented by
$\parallel\hat{\Delta}K_{w}\parallel_{F}^{2}$). Then we simply set $\beta$ as
0.1 (an empirical value that should not affect the model’s ability on other
tasks) and optimize the above objective to obtain the optimal $\Delta$. We
visualize some details of the optimization in Figure 2.

Figure 2: The details in the update process of Eq.(10). Here $K_{w}$
represents the keys of the knowledge to be washed and $V_{w}$ means the
corresponding values. Before the modification, $V_{w}$ is the output of layer
$W_{out}^{l}$ given the input $K_{w}$. Then we add $\Delta$ on $W_{out}^{l}$
where $\Delta$ is optimized via Eq.(10). Here $W_{out}^{l}$ is denoted as
$W_{0}$ in Section 5 for simplicity, and $K$ means the original keys in
$W_{0}$ before the modification (see Eq.(2)). The intuition is to unlearn the
knowledge in $K_{w}$ while not disturbing the model’s other ability encoded in
$W_{0}$.

###  5.1 Practical Consideration

##### Initialization of $\hat{\Delta}$.

We find that the optimization problem in Eq.(10) is a non-convex optimization
problem and is very sensitive to the initialization. During implementation, we
find that randomly initialized $\hat{\Delta}$ often leads to sub-optimal
solutions. To address this issue, we propose to use the delta matrixes from
MEMIT when performing the edits shown in Eq.(6). The intuition is that MEMIT
could achieve a fairly good tradeoff between the model’s reasoning ability and
knowledge washing. Then we run our optimization algorithm with the objective
in Eq.(10) on top of this initialization to achieve better performance.

##### Choices of $\beta$.

There are two strategies for choosing $\beta$. The first one is to set $\beta$
as a constant value such as $0.2$ which is to control the maginitude of the
modification on the model weights. Another strategy is to set the boundary
$\beta$ according to the original $\beta_{0}$ after the initialization.
Suppose the initialized $\hat{\Delta}$ from the above paragraph is
$\Delta_{0}$, then we have
$\beta_{0}=\frac{\parallel\Delta_{0}K\parallel^{2}}{\parallel
L\parallel^{2}}$. Then we loose $\beta_{0}$ with some small factor to allow
the space for optimization. Thus $\beta$ is usually chosen as $1.1*\beta_{0}$.

##### Successive Elimination of Target Knowledge Sets.

As our goal is to forget the knowledge in the knowledge set, when we are
updating multiple layers sequentially, we may exclude the factual relations
that have already been deleted after the update from the last layer. To this
end, before the update of every layer, we run the model to check the knowledge
that is still in the model and perform the optimization concerning this subset
of knowledge. In this way, we expect to achieve a more focused optimization
and better performance in knowledge washing.

###  5.2 Discussion of the Disentanglement of Knowledge and Reasoning

As demonstrated by Meng et al. (2022, 2023), the MLP (multi-layer perceptron)
layers in transformers primarily store knowledge. However, our research also
suggests that these layers significantly influence the model’s reasoning
capabilities. This assertion is supported by experiments showing that
modifications to the parameter $W_{0}$ can impact the model’s performance on
reasoning tasks. Therefore, we propose that MLP layers are critical for both
knowledge storage and reasoning processes. This paper explores strategies to
disentangle these two functions by identifying alternative weight matrices
that selectively diminish certain knowledge aspects while preserving, or
minimally affecting, reasoning abilities. The possibilities of achieving this
come from our hypothesis that knowledge storage and reasoning abilities can be
separated within transformers. In this paper, we show the possibility of the
disentanglement between knowledge and reasoning by washing a large amount of
knowledge from the model while only minimally affecting the reasoning
abilities.

##  6 Experiments

###  6.1 Experimental Setup

To demonstrate the effectiveness of our method, we compare it with various
knowledge editing and unlearning methods. The baselines for model-editing
include: (1) FT: Simply finetune the model on the factual sentences formed
from the triplets in $\mathcal{E}_{eos}$ in Eq.(6) (2) MEMIT (Meng et al.,
2023): This state-of-the-art method can edit multiple layers of the model to
perform thousands of edits simultaneously. (3) ME-FT (Model-Editing-FT)
(Gangadhar and Stratos, 2024), which finetunes the model with only the loss on
the span of $o_{i}$ in each sentence formed from
$(s_{i},r_{i},o_{i})\in\mathcal{E}_{w}$. Irrelevant sentences are constructed
as augmentations during training. For the knowledge unlearning category, the
baselines are: (1) FT-UL (Finetune-Unlearning): Finetune the model on the
sentences formed from the triplets $\mathcal{E}_{w}$ in Eq.(5) but with the
reverse (i.e. negative) next-word-prediction loss function; (2) WOH (Who is
Harry Potter) (Eldan and Russinovich, 2023): First train a reinforced model on
the unlearning dataset, then update the target model to diverge from the
reinforced model, based on the assumption that the reinforced model can better
retain the unlearning dataset; (3) SeUL (Selective Forgetting) (Wang et al.,
2024): Designates specific spans in the training data and uses a reversed
next-word-prediction loss function on these spans for training.

Consistent with previous studies (Meng et al., 2023; Gangadhar and Stratos,
2024), we employ GPT2-XL (1.5B parameters) and GPT-J-6B (6B parameters) as the
backbone models for knowledge washing. The datasets used in our experiments
are: (1) zsRE (Levy et al., 2017): A question-answering dataset with 19,086
facts. (2) CounterFactual (Meng et al., 2022): A dataset containing 21,929
counterfactual facts. After removing conflicting facts (Meng et al., 2023),
20,877 facts remain. (3) To facilitate large-scale knowledge washing, we
utilize the latest Wikipedia dump, processing the relations following the
guidelines provided in the repository222https://github.com/neelguha/simple-
wikidata-db. This results in 391,932,675 triplets. We then use gpt-3.5-turbo
to rewrite each triplet into a sentence containing both the subject and the
ground-truth answer. From 1,000,000 processed examples, we obtain 332,036
valid facts, creating the dataset referred to as Wiki-Latest.

For evaluation, we employ two metrics to assess the extent of knowledge
washing: (1) Accuracy: The model generates 10 tokens, and if the ground-truth
answer is among the decoded output, it is considered a correct prediction. The
accuracy is calculated as the percentage of correct predictions across the
entire dataset. (2) QA-F1-Score: Using the metric from LongBench (Bai et al.,
2023), we measure the F1-score between the generated output from the 10 tokens
and the ground-truth answer. We measure the model’s reasoning ability with the
library lm-evaluation-harness (Gao et al., 2023) on three tasks Lambda_openai
(Radford et al., 2019; Paperno et al., 2016), HellaSwag (Zellers et al.,
2019), and Arc_Easy (Clark et al., 2018). The descriptions of HellaSwag and
Arc_Easy are shown in Appendix C.1. For most of the tables in the main paper,
we only include the Accuracy and Perplexity from the evaluation results on
Lambda_openai and leave the full table with the performances of the other two
tasks in the appendix.

As for the implementation details, we perform all the experiments on eight
A6000-48GB GPUs, while every experiment can be run separately on one GPU. For
the implementation of MEMIT and ME-FT, we use their open-sourced code and
formulate the problem as setting the target knowledge set as
$\mathcal{E}_{eos}$ in Eq.(6). We manually implement FT to finetune on the
corresponding sentences from $\mathcal{E}_{eos}$. Then for the unlearning
methods, we reimplement WOH and SeUL following the method introduced in their
papers. We fix the number of training epochs as one so that the model’s
reasoning ability can be maximally maintained. For our method, we choose
$\beta=1.1\beta_{0}$ where $\beta_{0}$ is calculated from the parameters
initialized from the weights of MEMIT when editing the model with
$\mathcal{E}_{eos}$ in Eq.(6).

Table 1:  The experimental results of the model GPT2-XL on the datasets zsRE
and CounterFactual with different methods. The dataset zsRE contains 19086
factual statements in total, where GPT2-XL could answer 1212 facts correctly
and GPT-J-6B knows 1951 facts. Similarly, CounterFactual contains 20877 facts
in total where GPT2-XL knows 3680 facts and GPT-J-6B knows 5702 facts. We
highlight in red those results where the model is destroyed (the perplexity is
overly high), which are excluded from the accuracy comparison. Here Knowledge
refers to the evaluation on the knowledge set to be washed, and Reasoning
refers to the evaluation of different models on the dataset Lambda_openai
after performing knowledge washing with different methods.

| zsRE | CounterFactual
---|---|---
| Knowledge | Reasoning | Knowledge | Reasoning
|  Acc$\downarrow$ |  QA-F1$\downarrow$ |  Acc$\uparrow$ |  PPL$\downarrow$ |  Acc$\downarrow$ |  QA-F1$\downarrow$ |  Acc$\uparrow$ |  PPL$\downarrow$
GPT2-XL | 1.0000 | 0.3704 | 0.5121 | 10.63 | 1.0000 | 0.2647 | 0.5121 | 10.63
FT | 0.4208 | 0.2178 | 0.5275 | 9.72 | 0.1783 | 0.0930 | 0.5195 | 10.17
MEMIT | 0.0462 | 0.0379 | 0.5156 | 10.52 | 0.1929 | 0.1439 | 0.4879 | 11.81
ME-FT | 0.5091 | 0.2195 | 0.3881 | 21.95 | 0.1799 | 0.0878 | 0.3456 | 27.28
FT-UL | 0.0000 | 0.0000 | 0.1126 | $>10^{10}$ | 0.0000 | 0.0000 | 0.0000 | $>10^{10}$
WOH | 0.5182 | 0.2017 | 0.5082 | 10.17 | 0.5978 | 0.1615 | 0.4619 | 13.15
SeUL | 0.0957 | 0.0443 | 0.5108 | 10.66 | 0.0000 | 0.0000 | 0.2940 | 113.58
LaW | 0.0050 | 0.0039 | 0.5108 | 10.86 | 0.1091 | 0.0905 | 0.4741 | 12.73
GPT-J-6B | 1.0000 | 0.4043 | 0.6831 | 4.10 | 1.0000 | 0.4043 | 0.6831 | 4.10
FT | 0.6181 | 0.2538 | 0.6887 | 4.02 | 0.3995 | 0.1646 | 0.6837 | 4.08
MEMIT | 0.0553 | 0.0388 | 0.6815 | 4.14 | 0.2060 | 0.0759 | 0.6772 | 4.25
ME-FT | 0.0751 | 0.0349 | 0.5178 | 8.53 | 0.2139 | 0.1183 | 0.4071 | 11.15
FT-UL | 0.0000 | 0.0000 | 0.0000 | $>10^{10}$ | 0.0000 | 0.0000 | 0.0000 | $>10^{10}$
WOH | 0.6930 | 0.2829 | 0.6819 | 4.15 | 0.5396 | 0.1359 | 0.6833 | 4.19
SeUL | 0.7422 | 0.3032 | 0.6815 | 4.15 | 0.5393 | 0.1395 | 0.6693 | 4.35
LaW | 0.0454 | 0.0352 | 0.6701 | 4.35 | 0.0864 | 0.0334 | 0.6716 | 4.40

###  6.2 Overall Performance Comparison

####  6.2.1 Small-Scale Knowledge Washing

We first test the performances of our method on the small-scale knowledge-
washing tasks, i.e., forgetting the knowledge in zsRE and CounterFactual. We
report the results in Table 1. As shown in the table, our method can achieve
the best performance concerning the cleanness of knowledge washing (measured
by Accuracy and QA-F1-Score) while maintaining performance levels comparable
to the original model on reasoning tasks. As the dataset scale is not large,
it is shown in the table that WOH and SeUL, two fine-tuning-based methods
achieve some certain extent of knowledge washing and also successfully
maintain the model’s original ability, although there is already sign of
performance degradation as shown in the dataset CounterFactual (See the
performances of SeUL on GPT2-XL). Meanwhile, the method FT-UL could not
achieve reasonable results as the reverse training objective is overly fragile
to the training without more complicated regularization. We also show the
generated examples for visualization in Appendix C.2.3.

####  6.2.2 Large Scale Knowledge Washing

To further test the effectiveness of our method on large-scale knowledge
washing, we use the constructed large dataset Wiki-Latest on which we perform
knowledge washing. With 332,036 facts, we first go over the whole dataset to
find out all the facts that the model can predict correctly. Then we run our
algorithm to wash factual relations that the model knows about. The
performances of different methods on GPT2-XL and GPT-J-6B are reported in
Table 2. As shown in the table, LaW is shown to achieve the cleanest washing
in terms of the accuracy and QA-F1-score on the facts to be washed. We can
find that unlearning methods may easily destroy the model after drastic
updates. Compared with small-scale unlearning (shown in Table 1), the problems
with fine-tuning-based methods are more severe. Without proper regularization
during the update, the model’s abilities may be easily destroyed. On the
contrary, our method is more robust, which maintains comparable reasoning
ability while achieving the almost lowest accuracies in terms of knowledge
forgetting (only FT achieves lower accuracy, however, the perplexity and
accuracy in the reasoning tasks are drastically affected after the fine-tuning
process). For the generated examples after performing knowledge washing using
different methods on the model GPT2-XL, we visualize some results in Appendix
C.2.3.

Table 2: The experimental results of the model GPT2-XL on the dataset Wiki-Latest with different methods. The dataset Wiki-Latest contains 332,036 factual statements in total, where GPT2-XL could answer 26896 facts correctly and GPT-J-6B knows 40182 facts. We highlight in red those results where the model is destroyed (the perplexity is overly high), which are excluded from the accuracy comparison. The definition of Knowledge and Reasoning is the same as in Table 1. | GPT2-XL | GPT-J-6B
---|---|---
| Knowledge | Reasoning | Knowledge | Reasoning
|  Acc$\downarrow$ |  QA-F1$\downarrow$ |  Acc$\uparrow$ |  PPL$\downarrow$ |  Acc$\downarrow$ |  QA-F1$\downarrow$ |  Acc$\uparrow$ |  PPL$\downarrow$
Original | 1.0000 | 0.3734 | 0.5121 | 10.63 | 1.0000 | 0.2553 | 0.6831 | 4.10
FT | 0.0446 | 0.0256 | 0.1475 | 250.73 | 0.0159 | 0.0115 | 0.4349 | 13.00
MEMIT | 0.2972 | 0.2342 | 0.4906 | 11.44 | 0.2536 | 0.0753 | 0.6817 | 4.32
ME-FT | 0.0000 | 0.0000 | 0.0000 | $>10^{10}$ | 0.0000 | 0.0000 | 0.0000 | $>10^{10}$
FT-UL | 0.0000 | 0.0000 | 0.0000 | $>10^{10}$ | 0.0000 | 0.0000 | 0.0000 | $>10^{10}$
WOH | 0.4672 | 0.2227 | 0.1473 | 254.08 | 0.0009 | 0.0000 | 0.0171 | $>10^{10}$
SeUL | 0.0000 | 0.0000 | 0.0000 | $>10^{10}$ | 0.0004 | 0.0000 | 0.0002 | $>10^{10}$
LaW | 0.1926 | 0.1735 | 0.4657 | 13.27 | 0.1385 | 0.0846 | 0.6567 | 4.76
Table 3: Ablation study with different initialization of $\hat{\Delta}$.

| zsRE | CounterFactual
---|---|---
| Knowledge | Reasoning | Knowledge | Reasoning
|  Acc$\downarrow$ |  QA-F1$\downarrow$ |  Acc$\uparrow$ |  PPL$\downarrow$ |  Acc$\downarrow$ |  QA-F1$\downarrow$ |  Acc$\uparrow$ |  PPL$\downarrow$
GPT2-XL | 1.0000 | 0.3734 | 0.5121 | 10.63 | 1.0000 | 0.3734 | 0.5121 | 10.63
LaW ($\beta=0.2$, RI) | 0.8845 | 0.3274 | 0.5049 | 10.77 | 0.9158 | 0.2445 | 0.5082 | 10.86
LaW ($\beta=0.2$) | 0.0008 | 0.0008 | 0.4628 | 14.34 | 0.1258 | 0.1102 | 0.4708 | 13.04

###  6.3 Ablation Study

##### Ablation Study on Initialization of $\hat{\Delta}$

We compare the performance of LaW on the dataset zsRE and CounterFactual with
model GPT2-XL between using random initialization and using the initialization
from MEMIT. For random initialization, we sample a matrix matching the
dimension of $W_{0}$ (in Eq.(2)), filled with independent Gaussian random
variables scaled by a factor of $0.001$:
$\Delta_{0}=0.001\cdot\mathcal{N}(0,I)$. The results are reported in Table 3
(full table in Appendix C.2.2). When initializing from Gaussian distribution,
we do not have reference $\beta_{0}$ as in the initialization from MEMIT, so
we choose the constant $\beta=0.2$. Similarly, we also set $\beta=0.2$ when
using MEMIT initialization. The table shows the MEMIT initialization can boost
the performance drastically. The reason might be the optimization easily
achieves local minimum when using random optimization.

##### Ablation Study of Choices of $\beta$

As shown in Eq.(10), the hyper-parameter $\beta$ can control the tradeoff
between washing the knowledge in $K_{w}$ and maintaining the original
knowledge in $K$ (which may also be related to the model’s reasoning ability,
as we find that when this term is large the model’s reasoning ability may
degrade drastically). To study the effects of different $\beta$, we choose the
setting of dataset zsRE and CounterFactual with the model GPT2-XL to study the
effects of different $\beta$. The results are reported in Table 4 (full table
in Appendix C.2.2). From the table, we can see that as $\beta$ increases, the
knowledge is washed more thoroughly and the reasoning abilities are also
dropping, showing the tradeoff between knowledge washing and maintaining
reasoning abilities. We can also find that setting $\beta$ according to
$\beta_{0}$ can achieve better performances (see the performance comparison
between $\beta=1.2\beta_{0}$ and $\beta=0.2$ on the dataset CounterFactual),
which demonstrates the necessity of setting different $\beta$ for different
layers.

##### Ablation Study on Successive Elimination of Knowledge Set

In our practical considerations, before modifying every layer, we find the
facts in the knowledge set that the model can answer correctly and perform the
knowledge washing on the selected knowledge set. To study the effects of this
technique (denoted as SE), we conduct experiments with and without SE and
report the results in Table 5 (full table in Appendix C.2.2). The results show
that the algorithm can achieve a much cleaner washing with SE enabled, at the
expense of slightly affecting the reasoning abilities.

Table 4: Ablation study with different $\beta$ settings.  | zsRE | CounterFactual
---|---|---
| Knowledge | Reasoning | Knowledge | Reasoning
|  Acc$\downarrow$ |  QA-F1$\downarrow$ |  Acc$\uparrow$ |  PPL$\downarrow$ |  Acc$\downarrow$ |  QA-F1$\downarrow$ |  Acc$\uparrow$ |  PPL$\downarrow$
GPT2-XL | 1.0000 | 0.3734 | 0.5121 | 10.63 | 1.0000 | 0.3734 | 0.5121 | 10.63
$\beta=1.05\beta_{0}$ | 0.0074 | 0.0060 | 0.5127 | 10.74 | 0.1266 | 0.1070 | 0.4743 | 12.49
$\beta=1.1\beta_{0}$ | 0.0050 | 0.0039 | 0.5108 | 10.86 | 0.1091 | 0.0905 | 0.4741 | 12.73
$\beta=1.2\beta_{0}$ | 0.0008 | 0.0010 | 0.5073 | 11.06 | 0.0965 | 0.0853 | 0.4553 | 14.10
$\beta=1.5\beta_{0}$ | 0.0000 | 0.0003 | 0.4945 | 12.02 | 0.0655 | 0.0587 | 0.4314 | 16.31
$\beta=0.1$ | 0.0198 | 0.0166 | 0.5096 | 10.68 | 0.4318 | 0.2401 | 0.5063 | 10.82
$\beta=0.2$ | 0.0008 | 0.0008 | 0.4628 | 14.34 | 0.1258 | 0.1102 | 0.4708 | 13.04
$\beta=0.5$ | 0.0000 | 0.0000 | 0.2806 | 46.81 | 0.0242 | 0.0220 | 0.3169 | 36.23
Table 5: Ablation study with Successive Elimination technique enabled or disabled. | zsRE | CounterFactual
---|---|---
| Knowledge | Reasoning | Knowledge | Reasoning
|  Acc$\downarrow$ |  QA-F1$\downarrow$ |  Acc$\uparrow$ |  PPL$\downarrow$ |  Acc$\downarrow$ |  QA-F1$\downarrow$ |  Acc$\uparrow$ |  PPL$\downarrow$
GPT2-XL | 1.0000 | 0.3734 | 0.5121 | 10.63 | 1.0000 | 0.3734 | 0.5121 | 10.63
LaW | 0.0058 | 0.0043 | 0.5114 | 10.81 | 0.1091 | 0.0905 | 0.4741 | 12.73
w/o SE | 0.0322 | 0.0254 | 0.5160 | 10.52 | 0.1345 | 0.1137 | 0.4905 | 12.20

##  7 Conclusion, Limitation, and Future Work

In this paper, we introduce the Large Scale Knowledge Washing problem, which
means unlearning the existing knowledge in the model on a large scale. To
address this problem, we draw inspiration from model-editing methods and
propose Large Scale Washing (LaW), where we propose a new objective to remove
the corresponding knowledge from the MLP layers in the large language models
(LLMs), which is considered to store most of the knowledge in the LLMs.
Experimental results demonstrate the effectiveness of our method in washing
the knowledge in terms of the accuracies when prompted with queries related to
the knowledge set, while mostly maintaining the model’s reasoning ability. Our
work proposes an effective knowledge-washing algorithm and shows the
possibility of knowledge-reasoning disentanglement. One limitation is we
consider the knowledge set in a specific format, i.e., triplets, whereas
washing a large scale of knowledge in pure text where no triplets are
available might be more challenging. For future work, we aim to explore
washing the knowledge more thoroughly and extend our framework to other more
recent LLMs.

## References

  * Act [1996] A. Act.  Health insurance portability and accountability act of 1996.  _Public law_ , 104:191, 1996.
  * Alivanistos et al. [2022] D. Alivanistos, S. B. Santamaría, M. Cochez, J. Kalo, E. van Krieken, and T. Thanapalasingam.  Prompting as probing: Using language models for knowledge base construction.  In _LM-KBC@ISWC_ , volume 3274 of _CEUR Workshop Proceedings_ , pages 11–34. CEUR-WS.org, 2022.
  * Bai et al. [2023] Y. Bai, X. Lv, J. Zhang, H. Lyu, J. Tang, Z. Huang, Z. Du, X. Liu, A. Zeng, L. Hou, et al.  Longbench: A bilingual, multitask benchmark for long context understanding.  _arXiv preprint arXiv:2308.14508_ , 2023.
  * Black et al. [2021] S. Black, L. Gao, P. Wang, C. Leahy, and S. Biderman.  Gpt-neo: Large scale autoregressive language modeling with mesh-tensorflow.  _If you use this software, please cite it using these metadata_ , 58:2, 2021.
  * Chen and Yang [2023] J. Chen and D. Yang.  Unlearn what you want to forget: Efficient unlearning for llms.  _arXiv preprint arXiv:2310.20150_ , 2023.
  * Chen et al. [2022] W. Chen, Y. Chang, R. Zhang, J. Pu, G. Chen, L. Zhang, Y. Xi, Y. Chen, and C. Su.  Probing simile knowledge from pre-trained language models.  In _ACL (1)_ , pages 5875–5887. Association for Computational Linguistics, 2022.
  * Clark et al. [2018] P. Clark, I. Cowhey, O. Etzioni, T. Khot, A. Sabharwal, C. Schoenick, and O. Tafjord.  Think you have solved question answering? try arc, the ai2 reasoning challenge, 2018.
  * Eldan and Russinovich [2023] R. Eldan and M. Russinovich.  Who’s harry potter? approximate unlearning in llms.  _arXiv preprint arXiv:2310.02238_ , 2023.
  * Gangadhar and Stratos [2024] G. Gangadhar and K. Stratos.  Model editing by pure fine-tuning.  _CoRR_ , abs/2402.11078, 2024.
  * Gao et al. [2023] L. Gao, J. Tow, B. Abbasi, S. Biderman, S. Black, A. DiPofi, C. Foster, L. Golding, J. Hsu, A. Le Noac’h, H. Li, K. McDonell, N. Muennighoff, C. Ociepa, J. Phang, L. Reynolds, H. Schoelkopf, A. Skowron, L. Sutawika, E. Tang, A. Thite, B. Wang, K. Wang, and A. Zou.  A framework for few-shot language model evaluation, 12 2023.  URL https://zenodo.org/records/10256836.
  * Geva et al. [2020] M. Geva, R. Schuster, J. Berant, and O. Levy.  Transformer feed-forward layers are key-value memories.  _arXiv preprint arXiv:2012.14913_ , 2020.
  * Hartvigsen et al. [2022] T. Hartvigsen, S. Sankaranarayanan, H. Palangi, Y. Kim, and M. Ghassemi.  Aging with grace: Lifelong model editing with discrete key-value adaptors.  _arXiv preprint arXiv:2211.11031_ , 2022.
  * Hu et al. [2021] E. J. Hu, Y. Shen, P. Wallis, Z. Allen-Zhu, Y. Li, S. Wang, L. Wang, and W. Chen.  Lora: Low-rank adaptation of large language models.  _arXiv preprint arXiv:2106.09685_ , 2021.
  * Huang et al. [2023] Z. Huang, Y. Shen, X. Zhang, J. Zhou, W. Rong, and Z. Xiong.  Transformer-patcher: One mistake worth one neuron.  _arXiv preprint arXiv:2301.09785_ , 2023.
  * Isonuma and Titov [2024] M. Isonuma and I. Titov.  Unlearning reveals the influential training data of language models.  _arXiv preprint arXiv:2401.15241_ , 2024.
  * Legislature [2018] C. S. Legislature.  California consumer privacy act (CCPA).  "https://oag.ca.gov/privacy/ccpa", 2018.
  * Levy et al. [2017] O. Levy, M. Seo, E. Choi, and L. Zettlemoyer.  Zero-shot relation extraction via reading comprehension.  _arXiv preprint arXiv:1706.04115_ , 2017.
  * Liu et al. [2024a] S. Liu, Y. Yao, J. Jia, S. Casper, N. Baracaldo, P. Hase, X. Xu, Y. Yao, H. Li, K. R. Varshney, et al.  Rethinking machine unlearning for large language models.  _arXiv preprint arXiv:2402.08787_ , 2024a.
  * Liu et al. [2024b] Z. Liu, G. Dou, Z. Tan, Y. Tian, and M. Jiang.  Towards safer large language models through machine unlearning.  _arXiv preprint arXiv:2402.10058_ , 2024b.
  * Lu et al. [2022] X. Lu, S. Welleck, J. Hessel, L. Jiang, L. Qin, P. West, P. Ammanabrolu, and Y. Choi.  Quark: Controllable text generation with reinforced unlearning.  _Advances in neural information processing systems_ , 35:27591–27609, 2022.
  * Meng et al. [2022] K. Meng, D. Bau, A. Andonian, and Y. Belinkov.  Locating and editing factual associations in gpt.  _Advances in Neural Information Processing Systems_ , 35:17359–17372, 2022.
  * Meng et al. [2023] K. Meng, A. S. Sharma, A. J. Andonian, Y. Belinkov, and D. Bau.  Mass-editing memory in a transformer.  In _ICLR_. OpenReview.net, 2023.
  * Mitchell et al. [2022a] E. Mitchell, C. Lin, A. Bosselut, C. Finn, and C. D. Manning.  Fast model editing at scale.  In _ICLR_. OpenReview.net, 2022a.
  * Mitchell et al. [2022b] E. Mitchell, C. Lin, A. Bosselut, C. D. Manning, and C. Finn.  Memory-based model editing at scale.  In _ICML_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 15817–15831. PMLR, 2022b.
  * Paperno et al. [2016] D. Paperno, G. Kruszewski, A. Lazaridou, Q. N. Pham, R. Bernardi, S. Pezzelle, M. Baroni, G. Boleda, and R. Fernández.  The lambada dataset, Aug 2016.  URL https://doi.org/10.5281/zenodo.2630551.
  * Parliament and of the European Union [2016] E. Parliament and C. of the European Union.  General data protection regulation (GDPR), 2016.
  * Pawelczyk et al. [2023] M. Pawelczyk, S. Neel, and H. Lakkaraju.  In-context unlearning: Language models as few shot unlearners.  _arXiv preprint arXiv:2310.07579_ , 2023.
  * Radford et al. [2019] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever.  Language models are unsupervised multitask learners.  2019\.
  * Si et al. [2023] N. Si, H. Zhang, H. Chang, W. Zhang, D. Qu, and W. Zhang.  Knowledge unlearning for llms: Tasks, methods, and challenges.  _arXiv preprint arXiv:2311.15766_ , 2023.
  * Wang et al. [2024] L. Wang, X. Zeng, J. Guo, K.-F. Wong, and G. Gottlob.  Selective forgetting: Advancing machine unlearning techniques and evaluation in language models.  _arXiv preprint arXiv:2402.05813_ , 2024.
  * Yao et al. [2024] J. Yao, E. Chien, M. Du, X. Niu, T. Wang, Z. Cheng, and X. Yue.  Machine unlearning of pre-trained large language models.  _arXiv preprint arXiv:2402.15159_ , 2024.
  * Yao et al. [2023a] Y. Yao, P. Wang, B. Tian, S. Cheng, Z. Li, S. Deng, H. Chen, and N. Zhang.  Editing large language models: Problems, methods, and opportunities.  _CoRR_ , abs/2305.13172, 2023a.
  * Yao et al. [2023b] Y. Yao, X. Xu, and Y. Liu.  Large language model unlearning.  _arXiv preprint arXiv:2310.10683_ , 2023b.
  * Youssef et al. [2023] P. Youssef, O. A. Koras, M. Li, J. Schlötterer, and C. Seifert.  Give me the facts! A survey on factual knowledge probing in pre-trained language models.  In _EMNLP (Findings)_ , pages 15588–15605. Association for Computational Linguistics, 2023.
  * Zellers et al. [2019] R. Zellers, A. Holtzman, Y. Bisk, A. Farhadi, and Y. Choi.  Hellaswag: Can a machine really finish your sentence?  In _ACL (1)_ , pages 4791–4800. Association for Computational Linguistics, 2019.
  * Zhang et al. [2023] D. Zhang, P. Finckenberg-Broman, T. Hoang, S. Pan, Z. Xing, M. Staples, and X. Xu.  Right to be forgotten in the era of large language models: Implications, challenges, and solutions.  _arXiv preprint arXiv:2307.03941_ , 2023.
  * Zhao et al. [2024] Y. Zhao, L. Du, X. Ding, K. Xiong, Z. Sun, J. Shi, T. Liu, and B. Qin.  Deciphering the lmpact of pretraining data on large language models through machine unlearning.  _arXiv preprint arXiv:2402.11537_ , 2024.
  * Zheng et al. [2023] C. Zheng, L. Li, Q. Dong, Y. Fan, Z. Wu, J. Xu, and B. Chang.  Can we edit factual knowledge by in-context learning?  _arXiv preprint arXiv:2305.12740_ , 2023.
  * Zhu et al. [2020] C. Zhu, A. S. Rawat, M. Zaheer, S. Bhojanapalli, D. Li, F. X. Yu, and S. Kumar.  Modifying memories in transformer models.  _CoRR_ , abs/2012.00363, 2020.

##  Appendix A Mathematical Details of Preliminary

As demonstrated by MEMIT [Meng et al., 2023], the objective is to adjust
factual associations stored within the MLP layers of transformer-based,
decoder-only large language models. The conditional distribution of the next
token $x_{t}$, given by language model $G$, relies on the sequence of previous
tokens:

$P(x_{t}|x_{1},\cdots,x_{t-1})\triangleq
G(x_{1},\cdots,x_{t-1})=\textrm{softmax}(W_{y}h_{t-1}^{L}),$ (11)

where $L$ denotes the total number of layers in the transformer $G$, and
$h_{t-1}^{L}$ represents the hidden state of the $(t-1)$-th token at the
$L$-th layer, with $W_{y}$ being the language model head that predicts the
next word’s distribution over the vocabulary. Within transformers, the
computation of the state is articulated as follows:

$h_{t}^{l}=h_{t}^{l-1}(x)+\textrm{Attn}^{t}(h_{1}^{l-1},\cdots,h_{t}^{l-1})+W_{out}^{l}\sigma(W_{in}^{l}\gamma(h_{t}^{l})),$
(12)

where $h_{t}^{0}(x)$ is the embedding of the $t$-th token in the sentence $x$,
$\gamma$ represents layernorm, and $\sigma$ denotes the activation function.
Then knowledge editing requests are defined by:

$\mathcal{E}_{edit}=\\{s_{i},r_{i},o_{i}|i\\}\quad\textrm{s.t.},,\nexists
i,j.,(s_{i}=s_{j})\wedge(r_{i}=r_{j})\wedge(o_{i}\neq o_{j})$ (13)

In MEMIT [Meng et al., 2023], $W_{out}^{l}$, denoted as $W_{0}$, can act as
key-value memories, associating input keys $k_{i}\triangleq k_{i}^{l}$ with
corresponding values $v_{i}\triangleq v_{i}^{l}$ [Geva et al., 2020]. If
$W_{out}^{l}$ is dimensionally defined as $d_{1}\times d_{2}$ and stores $n$
memories, with $u$ new edits, then to modify the MLP layer $W_{out}^{l}$
(i.e., the matrix $W_{0}$), the following delta matrix $\Delta$ is solved:

$\Delta=\arg\min_{\hat{\Delta}}\parallel(W_{0}+\hat{\Delta})K_{1}-V_{1}\parallel_{F}^{2}$
(14)

where $K_{1}\in\mathbb{R}^{d_{2}\times(n+u)}$ represents a concatenation of
the original keys $K\in\mathbb{R}^{d_{2}\times n}$ stored in $W_{0}$ and keys
corresponding to the edit requests $K_{e}\in\mathbb{R}^{d_{2}\times u}$.
Similarly, $V_{1}\in\mathbb{R}^{d_{1}\times(n+u)}$ includes the original
values $V\in\mathbb{R}^{d_{1}\times n}$ and new values
$V_{e}\in\mathbb{R}^{d_{1}\times u}$.

Once the incremental matrix $\Delta$ is calculated, the matrix $W_{0}$ can be
updated to $W_{0}+\Delta$, representing the newly adjusted weight of the MLP
layer after edits. The closed-form solution for $\Delta$ is given by:

$\Delta=(V_{1}-W_{0}K_{1})K_{1}^{T}(K_{1}K_{1}^{T})^{-1}$ (15)

Given that $K_{1}$ is the concatenation of $K$ and $K_{e}$, the product
$K_{1}^{T}K_{1}$ equals $KK^{T}+K_{e}K_{e}^{T}$. With $K$ and $V$ representing
the keys and values associated with $W_{0}$, the optimal solution for $W_{0}$
under a least squares criterion is:

$W_{0}=\arg\min_{W}\|WK-V\|_{F}^{2}\implies W_{0}=VK^{T}(KK^{T})^{-1}\implies
W_{0}KK^{T}=VK^{T},$ (16)

Substituting these relationships into the equation for $\Delta$, we derive:

$\displaystyle\Delta$
$\displaystyle=(V_{1}K_{1}^{T}-W_{0}K_{1}K_{1}^{T})(K_{1}K_{1}^{T})^{-1}$ (17)
$\displaystyle=(W_{*}K_{e}^{T}+VK^{T}-W_{0}KK^{T}-W_{0}K_{e}K_{e}^{T})(K_{1}K_{1}^{T})^{-1}$
(18) $\displaystyle=(V_{e}-W_{0}K_{e})K_{e}^{T}(KK^{T}+K_{e}K_{e}^{T})^{-1}$
(19)

Define $R=V_{e}-W_{0}K_{e}$. Consequently, $\Delta$ simplifies to:

$\Delta=RK_{e}^{T}(KK^{T}+K_{e}K_{e}^{T})^{-1}$ (20)

This process enables the editing of an MLP layer within the transformer $G$ to
incorporate new relational data, following the solution of the equation for
each $K_{e}$ and $V_{e}$ from the editing requests. In the MEMIT approach
[Meng et al., 2023], $KK^{T}$ is pre-estimated and represented as $\lambda
C_{0}$, where $C_{0}$ is the average covariance matrix of $K$ and $\lambda$ is
a hyper-parameter typically on the order of 10,000.

When performing extensive model editing, modifying only one layer may lead to
robustness issues, while a more stable model can be achieved by minimizing the
magnitudes of parameter changes [Zhu et al., 2020]. Consequently, MEMIT
proposes modifying multiple layers to distribute the editing impact more
broadly [Meng et al., 2023]. This method involves spreading the residual
$R=V_{e}-W_{0}K_{e}$ across several layers. Let $L$ represent the index of the
deepest layer requiring modification such that the output of this layer
transitions from $W_{0}K_{e}$ to $V_{e}$. Define $\mathcal{R}$ as the set of
layer indices $\\{L-|\mathcal{R}|+1,\ldots,L\\}$ that require edits. For each
layer $l$ within $\mathcal{R}$, the necessary adjustments to the weights
$W^{l}$ are given by:

$\Delta^{l}=R^{l}{K_{e}^{l}}^{T}(K^{l}{K^{l}}^{T}+K_{e}^{l}{K_{e}^{l}}^{T})^{-1},$
(21)

where $R^{l}=\frac{R^{L}}{L-l+1}$ and $R^{L}=R$. These modifications are
applied sequentially from the lower to the upper layers, necessitating the
recalculation of $K_{e}^{l}$ as edits progress.

##  Appendix B Implementation Details

For the baselines, we train GPT-J-6B with LoRA [Hu et al., 2021]. we put the
configurations as below:

  1. 1.

FT. We set the learning rate as 1e-6 for GPT2 training and 1e-4 for the
training of GPT-J-6B and set the number of epochs as $5$. We find that with
more training, the model can easily achieve zero accuracy on the knowledge set
but also get overly high perplexity ($>10^{10}$) on the Lambda_openai dataset.

  2. 2.

MEMIT. This method has a hyperparameter $\lambda$ when estimating
$KK^{T}=\lambda C$ where $C$ is the average variable calculated on a large
dataset (see the details in Meng et al. [2023]). The configurations of
$\lambda$ in different settings are shown in Table 6. We found that with these
configurations the model can achieve good knowledge-washing accuracy while
mostly maintaining the model’s reasoning ability (minimal performance
degradation on reasoning tasks.)

  3. 3.

ME-FT. We use the code base from the open-sourced GitHub
page333https://github.com/au-revoir/model-editing-ft and use the
configurations from the website for zsRE and CounterFactual. For Wiki-Latest,
we choose the same configuration as CounterFactual with only the data source
file changed.

  4. 4.

FT-UL. We set the learning rate as 1e-6 for GPT2-XL and train for $1$ epoch
for every dataset, and set the learning rate as 1e-5 for GPT-J-6B and train
for $5$ epochs for every dataset (As LoRA training usually takes longer than
full-finetuning).

  5. 5.

WOH. We first train the reinforced model on the sentences formed from the
triplets $\mathcal{E}_{w}$ with the learning rate set as 1e-6 for 1 epoch,
then we adopt the objective Eq.(1) from the paper Eldan and Russinovich [2023]
to update the target model. During the second stage of training, we set the
learning rate as 5e-5 and train the model for 1 epoch.

  6. 6.

SeUL. We use the sentences formed from the triplets and only use the loss on
the span of the target $o_{i}$ in the triplet $(s_{i},r_{i},o_{i})$. For all
the models and the datasets, we train for 3 epochs with a learning rate set as
1e-6. We conduct full-finetuning on GPT2-XL and use LoRA to fine-tune
GPT-J-6B.

| zsRE | CounterFactual | Wiki-Latest
---|---|---|---
GPT2-XL | 20,000 | 20,000 | 100,000
GPT-J-6B | 50,000 | 100,000 | 100,000
Table 6: Configurations of MEMIT.

##  Appendix C Additional Experiments

###  C.1 Descriptions of the Reasoning Datasets

We conduct the reasoning experiments on three datasets: Lambda_openai [Radford
et al., 2019, Paperno et al., 2016], HellaSwag [Zellers et al., 2019], and
Arc_Easy [Clark et al., 2018]. The descriptions of these three datasets are as
follows:

  1. 1.

Lambda_openai [Paperno et al., 2016]: The LAMBADA dataset tests computational
text understanding via a word prediction task. It features narrative texts
where models must use broad context to predict the final word, rather than
just the last sentence. The dataset includes an original test split and
translations in German, Spanish, French, and Italian.

  2. 2.

HellaSwag [Zellers et al., 2019]: The HellaSwag dataset is a benchmark
designed for evaluating commonsense natural language inference (NLI)
capabilities. It challenges models to complete sentences in a way that aligns
with human common sense. The dataset prompts computational models to predict
plausible sentence endings, testing their understanding of everyday scenarios
and contexts.

  3. 3.

ARC_Easy [Clark et al., 2018]: The ARC_Easy dataset is a subset of the ARC
dataset, featuring grade-school level multiple-choice science questions that
are less challenging compared to the full set. It includes questions that were
correctly answered by standard algorithms.

###  C.2 Additional Experimental Results

####  C.2.1 Overall Performance Comparison

The overall performance comparisons with the performances on two other
reasoning benchmarks on zsRE, CounterFactual and Wiki-Latest are shown in
Table 10, Table 11 and Table 12, respectively.

####  C.2.2 Ablation Study

##### Ablation Study on Initialization of $\hat{\Delta}$

We put the full results of the ablation study with different initialization
methods in Table 7.

##### Ablation Study of Choices of $\beta$

We put the full results of different choices of $\beta$ in Table 8.

##### Ablation Study on Successive Elimination of Knowledge Set

The full results with Successive Elimination (SE) enabled or disabled are
shown in Table 9.

####  C.2.3 Case Study

In this section, we visualize the performances of different methods. We select
some examples from datasets zsRE, CounterFactual, and Wiki-Latest and show
them in Table 13. From the table, we can find that: (1) SeUL is usually
generating nonsense output which shows that the model’s fluency is affected.
(2) After knowledge washing, LaW is still able to answer these questions.
However, we do not force the model to remember any new knowledge, while only
forgetting the old knowledge. Consequently, the model may predict random
answers such as “Denmark” and “in the middle of the Finnish winter” or may
predict null answers like “None”. In contrast, other methods can either still
predict the correct answers (indicating the failure of unlearning), or start
generating nonsense. Compared with MEMIT, there is more chance for MEMIT to
output <|endoftext|> than LaW as this is the target of their editing, whereas
for LaW, we aim to disturb the output to generate random answers, which also
demonstrate the key difference: LaW aims to forget the existing knowledge
rather than injecting new factual relations.

Table 7: Ablation study with different $\beta$ settings. All settings are conducted with the weights initialized from MEMIT. Here “CF” refers to CounterFactual.  |  |  |  | Lambda_openai | hellaswag | arc_easy
---|---|---|---|---|---|---
|  |  Acc$\downarrow$ |  QA-F1$\downarrow$ | Acc | PPL | Acc_norm | Acc_norm
| GPT2-XL | 1.0000 | 0.3734 | 0.5121 | 10.63 | 0.5089 | 0.5105
CF |  LaW ($\beta=0.2$, RI) | 0.9158 | 0.2445 | 0.5082 | 10.86 | 0.5053 | 0.5059
LaW ($\beta=0.2$) | 0.1258 | 0.1102 | 0.4708 | 13.04 | 0.4941 | 0.4831
zsRE |  LaW ($\beta=0.2$, RI) | 0.8845 | 0.3274 | 0.5049 | 10.77 | 0.5081 | 0.5059
LaW ($\beta=0.2$) | 0.0008 | 0.0008 | 0.4628 | 14.34 | 0.4924 | 0.4800
Table 8: Ablation study with different $\beta$ settings. All settings are conducted with the weights initialized from MEMIT. Here “CF” refers to CounterFactual. |  |  |  | Lambda_openai | hellaswag | arc_easy
---|---|---|---|---|---|---
|  |  Acc$\downarrow$ |  QA-F1$\downarrow$ | Acc | PPL | Acc_norm | Acc_norm
| GPT2-XL | 1.0000 | 0.3734 | 0.5121 | 10.63 | 0.5089 | 0.5105
CF | $\beta=1.05\beta_{0}$ | 0.1266 | 0.1070 | 0.4743 | 12.49 | 0.5038 | 0.4950
$\beta=1.1\beta_{0}$ | 0.1155 | 0.0995 | 0.4708 | 12.93 | 0.5017 | 0.4917
$\beta=1.2\beta_{0}$ | 0.0965 | 0.0853 | 0.4553 | 14.10 | 0.4941 | 0.4829
$\beta=1.5\beta_{0}$ | 0.0655 | 0.0587 | 0.4314 | 16.31 | 0.4819 | 0.4672
$\beta=0.1$ | 0.4318 | 0.2401 | 0.5063 | 10.82 | 0.5055 | 0.5069
| $\beta=0.2$ | 0.1258 | 0.1102 | 0.4708 | 13.04 | 0.4941 | 0.4831
| $\beta=0.5$ | 0.0242 | 0.0220 | 0.3169 | 36.23 | 0.4209 | 0.4176
zsRE | $\beta=1.05\beta_{0}$ | 0.0074 | 0.0060 | 0.5127 | 10.74 | 0.5114 | 0.5096
$\beta=1.1\beta_{0}$ | 0.0050 | 0.0039 | 0.5108 | 10.86 | 0.5079 | 0.5118
$\beta=1.2\beta_{0}$ | 0.0008 | 0.0010 | 0.5073 | 11.06 | 0.5064 | 0.5126
$\beta=1.5\beta_{0}$ | 0.0000 | 0.0003 | 0.4945 | 12.02 | 0.4960 | 0.5126
$\beta=0.1$ | 0.0198 | 0.0166 | 0.5096 | 10.68 | 0.5097 | 0.5108
| $\beta=0.2$ | 0.0008 | 0.0008 | 0.4628 | 14.34 | 0.4924 | 0.4800
| $\beta=0.5$ | 0.0000 | 0.0000 | 0.2806 | 46.81 | 0.4242 | 0.4212
Table 9: Ablation study with Successive Elimination technique enabled or disabled. Here “CF” refers to CounterFactual. |  |  |  | Lambda_openai | hellaswag | arc_easy
---|---|---|---|---|---|---
|  |  Acc$\downarrow$ |  QA-F1$\downarrow$ | Acc | PPL | Acc_norm | Acc_norm
| GPT2-XL | 1.0000 | 0.3734 | 0.5121 | 10.63 | 0.5089 | 0.5105
CF | LaW | 0.1091 | 0.0905 | 0.4741 | 12.73 | 0.5021 | 0.4909
w/o SE | 0.1345 | 0.1137 | 0.4905 | 12.20 | 0.4843 | 0.5034
zsRE | LaW | 0.0058 | 0.0043 | 0.5114 | 10.81 | 0.5087 | 0.5114
w/o SE | 0.0322 | 0.0254 | 0.5160 | 10.52 | 0.5103 | 0.5143
Wiki-Latest | LaW | 0.1926 | 0.1735 | 0.4657 | 13.27 | 0.4865 | 0.4975
w/o SE | 0.2398 | 0.2038 | 0.4788 | 12.40 | 0.4940 | 0.5097
Table 10:  The experimental results of the model GPT2-XL on the dataset zsRE with different methods. The dataset zsRE contains 19086 factual statements in total, where GPT2-XL could answer 1212 facts correctly and GPT-J-6B knows 1951 facts. We highlight in red those results where the model is destroyed (the perplexity is overly high), which are excluded from the accuracy comparison. | zsRE | Lambada_openai | hellaswag | arc_easy
---|---|---|---|---
| Acc$\downarrow$ | QA-F1$\downarrow$ | Acc$\uparrow$ | PPL$\downarrow$ | Acc_norm$\uparrow$ | Acc_norm$\uparrow$
GPT2-XL | 1.0000 | 0.3704 | 0.5121 | 10.63 | 0.5089 | 0.5105
FT | 0.4208 | 0.2178 | 0.5275 | 9.72 | 0.5058 | 0.4815
MEMIT | 0.0462 | 0.0379 | 0.5156 | 10.52 | 0.5109 | 0.5126
ME-FT | 0.5091 | 0.2195 | 0.3881 | 21.95 | 0.5052 | 0.5471
FT-UL | 0.0000 | 0.0000 | 0.1126 | $>10^{10}$ | 0.3557 | 0.2513
WOH | 0.5182 | 0.2017 | 0.5082 | 10.17 | 0.4957 | 0.4941
SeUL | 0.0957 | 0.0443 | 0.5108 | 10.66 | 0.5072 | 0.4541
LaW | 0.0058 | 0.0043 | 0.5114 | 10.81 | 0.5087 | 0.5114
GPT-J-6B | 1.0000 | 0.4043 | 0.6831 | 4.10 | 0.6625 | 0.6225
FT | 0.6181 | 0.2538 | 0.6887 | 4.02 | 0.6646 | 0.6237
MEMIT | 0.0553 | 0.0388 | 0.6815 | 4.14 | 0.6630 | 0.6250
ME-FT | 0.0751 | 0.0349 | 0.5178 | 8.53 | 0.6156 | 0.6263
FT-UL | 0.0000 | 0.0000 | 0.0000 | $>10^{10}$ | 0.2597 | 0.2500
WOH | 0.6930 | 0.2829 | 0.6819 | 4.15 | 0.6638 | 0.6098
SeUL | 0.7422 | 0.3032 | 0.6815 | 4.15 | 0.6618 | 0.6111
LaW | 0.0454 | 0.0352 | 0.6701 | 4.35 | 0.6575 | 0.6128
Table 11: The experimental results of the model GPT2-XL on the dataset CounterFactual with different methods. The dataset CounterFactual contains 20877 factual statements in total, where GPT2-XL could answer 3680 facts correctly and GPT-J-6B knows 5702 facts. We highlight in red those results where the model is destroyed (the perplexity is overly high), which are excluded from the accuracy comparison. | CounterFactual | Lambada_openai | hellaswag | arc_easy
---|---|---|---|---
| Acc$\downarrow$ | QA-F1$\downarrow$ | Acc$\uparrow$ | PPL$\downarrow$ | Acc_norm$\uparrow$ | Acc_norm$\uparrow$
GPT2-XL | 1.0000 | 0.2647 | 0.5121 | 10.63 | 0.5089 | 0.5105
FT | 0.1783 | 0.0930 | 0.5195 | 10.17 | 0.4978 | 0.4928
MEMIT | 0.1929 | 0.1439 | 0.4879 | 11.81 | 0.5005 | 0.5051
ME-FT | 0.1799 | 0.0878 | 0.3456 | 27.28 | 0.3956 | 0.3354
FT-UL | 0.0000 | 0.0000 | 0.0000 | $>10^{10}$ | 0.2753 | 0.2529
WOH | 0.5978 | 0.1615 | 0.4619 | 13.15 | 0.4763 | 0.4886
SeUL | 0.0000 | 0.0000 | 0.2940 | 113.58 | 0.4401 | 0.3333
Ours | 0.1091 | 0.0905 | 0.4741 | 12.73 | 0.5021 | 0.4909
GPT-J-6B | 1.0000 | 0.2553 | 0.6831 | 4.10 | 0.6625 | 0.6225
FT | 0.3995 | 0.1646 | 0.6837 | 4.08 | 0.6640 | 0.6157
MEMIT | 0.2060 | 0.0759 | 0.6772 | 4.25 | 0.6570 | 0.6166
ME-FT | 0.2139 | 0.1183 | 0.4071 | 11.15 | 0.5844 | 0.5421
FT-UL | 0.0000 | 0.0000 | 0.0000 | $>10^{10}$ | 0.2579 | 0.2542
WOH | 0.5396 | 0.1359 | 0.6833 | 4.19 | 0.6662 | 0.6111
SeUL | 0.5393 | 0.1395 | 0.6693 | 4.35 | 0.6620 | 0.6641
Ours | 0.0864 | 0.0334 | 0.6716 | 4.40 | 0.6495 | 0.5951
Table 12: The experimental results of the model GPT2-XL on the dataset Wiki-Latest with different methods. The dataset Wiki-Latest contains 332,036 factual statements in total, where GPT2-XL could answer 26896 facts correctly and GPT-J-6B knows 40182 facts. We highlight in red those results where the model is destroyed (the perplexity is overly high), which are excluded from the accuracy comparison. | Wiki-Latest | Lambada_openai | hellaswag | arc_easy
---|---|---|---|---
| Acc$\downarrow$ | QA-F1$\downarrow$ | Acc | PPL | Acc_norm | Acc_norm
GPT2-XL | 1.0000 | 0.3734 | 0.5121 | 10.63 | 0.5089 | 0.5105
FT | 0.0446 | 0.0256 | 0.1475 | 250.73 | 0.4315 | 0.4125
MEMIT | 0.2972 | 0.2342 | 0.4906 | 11.44 | 0.5004 | 0.5177
ME-FT | 0.0000 | 0.0000 | 0.0000 | $>10^{10}$ | 0.3191 | 0.2744
FT-UL | 0.0000 | 0.0000 | 0.0000 | $>10^{10}$ | 0.2603 | 0.2441
WOH | 0.4672 | 0.2227 | 0.1473 | 254.08 | 0.3546 | 0.3712
SeUL | 0.0000 | 0.0000 | 0.0000 | $>10^{10}$ | 0.2603 | 0.2339
Ours | 0.1926 | 0.1735 | 0.4657 | 13.27 | 0.4865 | 0.4975
GPT-J-6B | 1.0000 | 0.2553 | 0.6831 | 4.10 | 0.6625 | 0.6225
FT | 0.0159 | 0.0115 | 0.4349 | 13.00 | 0.5332 | 0.4920
MEMIT | 0.2536 | 0.0753 | 0.6817 | 4.32 | 0.6600 | 0.5892
ME-FT | 0.0000 | 0.0000 | 0.0000 | $>10^{10}$ | 0.2594 | 0.2555
FT-UL | 0.0000 | 0.0000 | 0.0000 | $>10^{10}$ | 0.2559 | 0.2449
WOH | 0.0009 | 0.0000 | 0.0171 | $>10^{10}$ | 0.2484 | 0.2529
SeUL | 0.0004 | 0.0000 | 0.0000 | $>10^{10}$ | 0.2580 | 0.2504
Prompt |  What fictional universe is Mister Miracle a part of? Answer: |  Magnus Carlsen, who holds a citizenship from |  Yago Fernando da Silva speaks and writes
---|---|---|---
Ground Truth |  The DC Universe |  Norway |  in Portuguese
MEMIT |  <|endoftext|> |  Norway |  English
ME-FT |  Superman’s family is the only known superpowered group |  Norway |  $\emptyset$ (empty space)
WOH |  The universe of the comic book. |  the former Soviet Union |  about the Brazilian and Portuguese language
SeUL |  $\backslash$n$\backslash$nA:$\backslash$n$\backslash$nB:$\backslash$n$\backslash$n |  -the- shadows as a a the a very |  synonymous synonymous synonymous
LaW |  None |  Denmark |  iban chat
Table 13: Case studies of different methods on the instance of dataset zsRE,
CounterFactual, and Wiki-Latest in the first, second, and third column,
respectively.


}\bar{{\boldsymbol{y}}}_{\mathcal{I}_{2}}\end{subarray}}).$

So, a pair of valid support and multiplier has been recovered. However,
$\bar{{\boldsymbol{x}}}\notin\mathbb{F}_{q^{m}}^{n}$, because
$\bar{x}_{n}=\infty$. The last question is therefore how to get a valid pair
of support and multiplier such that both are defined over
$\mathbb{F}_{q^{m}}$, i.e. how to get the alternant representation. In other
words, we need to determine some $f\in GL_{2}(\mathbb{F}_{q^{m}})$ and
$\lambda\in\mathbb{F}_{q^{m}}\setminus\\{0\\}$ such that

$\bar{x}_{i}^{\prime}=f(\bar{x}_{i})\in\mathbb{F}_{q^{m}},\quad\forall
i\in\llbracket 1,n\rrbracket$

and

$\bar{y}_{i}^{\prime}=\lambda\theta(f,\bar{x}_{i})^{r-1}\bar{y}_{i}\in\mathbb{F}_{q^{m}},\quad\forall
i\in\llbracket 1,n\rrbracket.$

We observe that, since there are only $n-1$ coordinates of
$\bar{{\boldsymbol{x}}}$ in $\mathbb{F}_{q^{m}}$ and $n-1<q^{m}$, there exists
at least one element $\hat{x}\in\mathbb{F}_{q^{m}}$ that is different from all
$\bar{{\boldsymbol{x}}}$ coordinates. We also remark that $\hat{x}\neq 0$,
since $\bar{x}_{n-2}=0$, so the map $f$ on $\bar{\mathbb{F}}_{q^{m}}$

$f\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{z}{z-\hat{x}}$

is induced by an element of the linear group. We have $\theta(f,z)=z-\hat{x}$
if $z\in\mathbb{F}_{q^{m}}$ and $\theta(f,\infty)=1$ and we choose
$\lambda=1$. Therefore

$\displaystyle\bar{x}_{i}^{\prime}=\frac{\bar{x}_{i}}{\bar{x}_{i}-\hat{x}},$
$\displaystyle\quad i\in\llbracket 1,n-1\rrbracket,$
$\displaystyle\bar{x}_{n}^{\prime}=1,$
$\displaystyle\bar{y}_{i}^{\prime}=(\bar{x}_{i}-\hat{x})^{r-1}\bar{y}_{i},$
$\displaystyle\quad i\in\llbracket 1,n-1\rrbracket,$
$\displaystyle\bar{y}_{n}^{\prime}=\bar{y}_{n}=1.$

We finally obtained a support and a multiplier with coordinates over
$\mathbb{F}_{q^{m}}$ that define the public code. This concludes the key-
recovery attack on high-rate random alternant codes.

##  5\. Conclusion

### Breaking the $m=2$ barrier.

Even if the first step of the attack, namely the derivation of an alternant
code of degree $3$ from the original alternant code is reminiscent of the
filtration attack [COT14, COT17] which allowed to break a McEliece scheme
based on wild Goppa codes of extension degree $2$, it differs in a crucial
way. In [COT14, COT17] building this decreasing sequence of codes is based on
taking the shortening of the original Goppa code and square codes of it. This
method is bound to fail when the extension degree $m$ is greater than $2$ as
explained in [COT17, §III]. This is a pity, because the square code is much
easier to understand in this case since it retains the polynomial structure of
the generalized Reed-Solomon super-code. To go beyond the $m=2$ barrier, it is
mandatory to look for the the square of shortenings of the dual of the
Goppa/alternant code instead. This square is much more difficult to
understand, since taking the dual of a subfield subcode as is the case here
yields by Delsarte’s theorem the trace code of a generalized Reed-Solomon code
which loses a lot of its polynomial description. This is certainly one of the
main difficulties that had to be overcome to transform the distinguisher of
[FGO+11] into an attack.

This is precisely what is achieved here. Besides shedding some light (together
with [MT22]) on the structure of the square of such dual codes, this paper
also introduces some other crucial ideas. The first one being the crucial role
of being a generic alternant code rather than a Goppa code and then the
condition $r\geqslant q+1$ which is crucial for our main result, Theorem 17 to
hold. It is rather surprising that right now it seems that this filtration
strategy needs apparently additional ideas to make it work in the particular
case of Goppa codes as observed in Subsection 3.2 despite the fact that Goppa
codes are even more structured than plain alternant codes. However there are
clearly reasons to believe that this paper has solved the main issue when it
comes to transform the distinguisher of [FGO+11] into an attack, which is to
be able to work with the dual of the alternant/Goppa code, since this is the
crux in breaking the $m=2$ barrier. Therefore it is tempting to conjecture
that Goppa codes, at least in the regime where they are distinguishable from
random codes (which applies in particular to the CFS scheme [CFS01]) should
eventually be attacked in polynomial by some variation the attack that has
been given here.

### Understanding the Gröbner basis approach.

The filtration approach which amounts here to construct a nested sequence of
dual of alternant codes of decreasing degree results in a final alternant code
of degree $3$ in the case at hand. From here, a dedicated Gröbner basis is
used to recover the polynomial structure of the alternant code. This approach
is able to take into account in a very efficient way the fact that the
multiplier and the support that are sought should satisfy certain non standard
constraints (all the entries of the multiplier are non zero whereas all the
entries of the support are distinct). Taking these constraints into account as
we do here results in speeding up significantly the algebraic system solving
by adding many new low degree equations to the algebraic system. When the code
is a Goppa code it turns out that solving the relevant system behaves a little
bit differently (as for the case of the filtration). However, unlike the case
of the filtration where right now this part of the attack does not work at
all, it seems that here even if the Gröbner basis computation consists of more
steps, solving the whole system should still be polynomial. Actually there are
reasons to conjecture that the Gröbner basis approach stays of polynomial
complexity for recovering the polynomial structure of an alternant code of
degree $4$ and even potentially beyond this, say up to a constant degree. More
generally, this raises the issue of understanding how the complexity of
recovering the polynomial structure of a degree $r$ alternant/Goppa code
through this Gröbner basis approach scales with $r$. An obvious application of
this study would be to be able to increase the values of the field size $q$
for which we still have a polynomial attack. This could also allow to get a
better understanding how the McEliece resists to this algebraic approach in
general and is desirable in the light of the ongoing NIST competition where
the McEliece cryptosystem is an alternate fourth round candidate.

## References

  * [ABC+20] Martin Albrecht, Daniel J. Bernstein, Tung Chou, Carlos Cid, Jan Gilcher, Tanja Lange, Varun Maram, Ingo von Maurich, Rafael Mizoczki, Ruben Niederhagen, Edoardo Persichetti, Kenneth Paterson, Christiane Peters, Peter Schwabe, Nicolas Sendrier, Jakub Szefer, Cen Jung Tjhai, Martin Tomlinson, and Wang Wen.  Classic McEliece (merger of Classic McEliece and NTS-KEM).  https://classic.mceliece.org, October 2020.  Third round finalist of the NIST post-quantum cryptography call.
  * [BBB+17] Gustavo Banegas, Paulo S.L.M Barreto, Brice Odilon Boidje, Pierre-Louis Cayrel, Gilbert Ndollane Dione, Kris Gaj, Cheikh Thiécoumba Gueye, Richard Haeussler, Jean Belo Klamti, Ousmane N’diaye, Duc Tri Nguyen, Edoardo Persichetti, and Jefferson E. Ricardini.  DAGS : Key encapsulation for dyadic GS codes.  https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/DAGS.zip, November 2017.  First round submission to the NIST post-quantum cryptography call.
  * [BCGO09] Thierry P. Berger, Pierre-Louis Cayrel, Philippe Gaborit, and Ayoub Otmani.  Reducing key length of the McEliece cryptosystem.  In Bart Preneel, editor, Progress in Cryptology - AFRICACRYPT 2009, volume 5580 of LNCS, pages 77–97, Gammarth, Tunisia, June 21-25 2009.
  * [Ber00] Thierry P. Berger.  On the cyclicity of Goppa codes, parity-check subcodes of Goppa codes and extended Goppa codes.  Finite Fields Appl., 6(3):255–281, 2000.
  * [BJMM12] Anja Becker, Antoine Joux, Alexander May, and Alexander Meurer.  Decoding random binary linear codes in $2^{n/20}$: How $1+1=0$ improves information set decoding.  In Advances in Cryptology - EUROCRYPT 2012, LNCS. Springer, 2012\.
  * [BLM11] Paulo Barreto, Richard Lindner, and Rafael Misoczki.  Monoidic codes in cryptography.  In Post-Quantum Cryptography 2011, volume 7071 of LNCS, pages 179–199. Springer, 2011.
  * [BLP10] Daniel J. Bernstein, Tanja Lange, and Christiane Peters.  Wild McEliece.  In Alex Biryukov, Guang Gong, and Douglas R. Stinson, editors, Selected Areas in Cryptography, volume 6544 of LNCS, pages 143–158, 2010\.
  * [BLP11] Daniel J. Bernstein, Tanja Lange, and Christiane Peters.  Wild McEliece Incognito.  In Bo-Yin Yang, editor, Post-Quantum Cryptography 2011, volume 7071 of LNCS, pages 244–254. Springer Berlin Heidelberg, 2011.
  * [BM17] Leif Both and Alexander May.  Optimizing BJMM with Nearest Neighbors: Full Decoding in $2^{2/21n}$ and McEliece Security.  In WCC Workshop on Coding and Cryptography, September 2017.
  * [CBB+17] Alain Couvreur, Magali Bardet, Élise Barelli, Olivier Blazy, Rodolfo Canto Torres, Phillipe Gaborit, Ayoub Otmani, Nicolas Sendrier, and Jean-Pierre Tillich.  BIG QUAKE.  https://bigquake.inria.fr, November 2017.  NIST Round 1 submission for Post-Quantum Cryptography.
  * [CC98] Anne Canteaut and Florent Chabaud.  A new algorithm for finding minimum-weight words in a linear code: Application to McEliece’s cryptosystem and to narrow-sense BCH codes of length 511.  IEEE Trans. Inform. Theory, 44(1):367–378, 1998.
  * [CCMZ15] Igniacio Cascudo, Ronald Cramer, Diego Mirandola, and Gilles Zémor.  Squares of random linear codes.  IEEE Trans. Inform. Theory, 61(3):1159–1173, 3 2015.
  * [CFS01] Nicolas Courtois, Matthieu Finiasz, and Nicolas Sendrier.  How to achieve a McEliece-based digital signature scheme.  In Advances in Cryptology - ASIACRYPT 2001, volume 2248 of LNCS, pages 157–174, Gold Coast, Australia, 2001. Springer.
  * [CGG+14] Alain Couvreur, Philippe Gaborit, Valérie Gauthier-Umaña, Ayoub Otmani, and Jean-Pierre Tillich.  Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes.  Des. Codes Cryptogr., 73(2):641–666, 2014.
  * [CMCP17] Alain Couvreur, Irene Márquez-Corbella, and Ruud Pellikaan.  Cryptanalysis of McEliece cryptosystem based on algebraic geometry codes and their subcodes.  IEEE Trans. Inform. Theory, 63(8):5404–5418, 8 2017.
  * [COT14] Alain Couvreur, Ayoub Otmani, and Jean-Pierre Tillich.  New identities relating wild Goppa codes.  Finite Fields Appl., 29:178–197, 2014.
  * [COT17] Alain Couvreur, Ayoub Otmani, and Jean-Pierre Tillich.  Polynomial time attack on wild McEliece over quadratic extensions.  IEEE Trans. Inform. Theory, 63(1):404–427, 1 2017.
  * [Del75] Philippe Delsarte.  On subfield subcodes of modified Reed-Solomon codes.  IEEE Trans. Inform. Theory, 21(5):575–576, 1975.
  * [Dür87] Arne Dür.  The automorphism groups of Reed-Solomon codes.  Journal of Combinatorial Theory, Series A, 44:69–82, 1987.
  * [FGLM93] Jean-Charles Faugère, Patrizia M. Gianni, Daniel Lazard, and Teo Mora.  Efficient computation of zero-dimensional gröbner bases by change of ordering.  J. Symbolic Comput., 16(4):329–344, 1993.
  * [FGO+11] Jean-Charles Faugère, Valérie Gauthier, Ayoub Otmani, Ludovic Perret, and Jean-Pierre Tillich.  A distinguisher for high rate McEliece cryptosystems.  In Proc. IEEE Inf. Theory Workshop- ITW 2011, pages 282–286, Paraty, Brasil, October 2011.
  * [FGO+13] Jean-Charles Faugère, Valérie Gauthier, Ayoub Otmani, Ludovic Perret, and Jean-Pierre Tillich.  A distinguisher for high rate McEliece cryptosystems.  IEEE Trans. Inform. Theory, 59(10):6830–6844, October 2013.
  * [FOPT10] Jean-Charles Faugère, Ayoub Otmani, Ludovic Perret, and Jean-Pierre Tillich.  Algebraic cryptanalysis of McEliece variants with compact keys.  In Advances in Cryptology - EUROCRYPT 2010, volume 6110 of LNCS, pages 279–298, 2010.
  * [GUL09] Valérie Gauthier-Umaña and Gregor Leander.  Practical key recovery attacks on two McEliece variants, 2009.  IACR Cryptology ePrint Archive, Report2009/509.
  * [HP03] W. Cary Huffman and Vera Pless.  Fundamentals of error-correcting codes.  Cambridge University Press, Cambridge, 2003.
  * [KT17] Ghazal Kachigar and Jean-Pierre Tillich.  Quantum information set decoding algorithms.  In Post-Quantum Cryptography 2017, volume 10346 of LNCS, pages 69–89, Utrecht, The Netherlands, June 2017. Springer.
  * [LS01] Pierre Loidreau and Nicolas Sendrier.  Weak keys in the McEliece public-key cryptosystem.  IEEE Trans. Inform. Theory, 47(3):1207–1211, 2001.
  * [MB09] Rafael Misoczki and Paulo Barreto.  Compact McEliece keys from Goppa codes.  In Selected Areas in Cryptography, Calgary, Canada, August 13-14 2009.
  * [McE78] Robert J. McEliece.  A Public-Key System Based on Algebraic Coding Theory, pages 114–116.  Jet Propulsion Lab, 1978.  DSN Progress Report 44.
  * [MMT11] Alexander May, Alexander Meurer, and Enrico Thomae.  Decoding random linear codes in $O(2^{0.054n})$.  In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology - ASIACRYPT 2011, volume 7073 of LNCS, pages 107–124. Springer, 2011.
  * [MO15] Alexander May and Ilya Ozerov.  On computing nearest neighbors with applications to decoding of binary linear codes.  In E. Oswald and M. Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015, volume 9056 of LNCS, pages 203–228. Springer, 2015.
  * [MP12] Irene Márquez-Corbella and Ruud Pellikaan.  Error-correcting pairs for a public-key cryptosystem.  CBC 2012, Code-based Cryptography Workshop, 2012.  Available on http://www.win.tue.nl/~ruudp/paper/59.pdf.
  * [MS86] Florence J. MacWilliams and Neil J. A. Sloane.  The Theory of Error-Correcting Codes.  North–Holland, Amsterdam, fifth edition, 1986.
  * [MT21] Rocco Mora and Jean-Pierre Tillich.  On the dimension and structure of the square of the dual of a Goppa code.  preprint, 2021.
  * [MT22] Rocco Mora and Jean-Pierre Tillich.  On the dimension and structure of the square of the dual of a Goppa code.  In WCC 2022 - Workshop on Coding Theory and Cryptography, 2022\.
  * [Nie86] Harald Niederreiter.  Knapsack-type cryptosystems and algebraic coding theory.  Problems of Control and Information Theory, 15(2):159–166, 1986\.
  * [Ran15] Hugues Randriambololona.  On products and powers of linear codes under componentwise multiplication.  In Algorithmic arithmetic, geometry, and coding theory, volume 637 of Contemp. Math., pages 3–78. Amer. Math. Soc., Providence, RI, 2015\.
  * [RSA78] Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman.  A method for obtaining digital signatures and public-key cryptosystems.  Commun. ACM, 21(2):120–126, 1978.
  * [Sen00] Nicolas Sendrier.  Finding the permutation between equivalent linear codes: The support splitting algorithm.  IEEE Trans. Inform. Theory, 46(4):1193–1203, 2000.
  * [Sho94] Peter W. Shor.  Algorithms for quantum computation: Discrete logarithms and factoring.  In S. Goldwasser, editor, FOCS, pages 124–134, 1994.
  * [SS92] Vladimir Michilovich Sidelnikov and S.O. Shestakov.  On the insecurity of cryptosystems based on generalized Reed-Solomon codes.  Discrete Math. Appl., 1(4):439–444, 1992.
  * [Ste88] Jacques Stern.  A method for finding codewords of small weight.  In G. D. Cohen and J. Wolfmann, editors, Coding Theory and Applications, volume 388 of LNCS, pages 106–113. Springer, 1988.

##  Appendix A Further results about trace codes

We will state and prove here a simple result on the extension of trace codes
which will be useful in our context.

######  Proposition 41.

Let $\mathscr{C}\subseteq\mathbb{F}_{q^{m}}^{n}$ be an $\mathbb{F}_{q^{m}}$\-
linear code. Then

$\textrm{Tr}\left(\mathscr{C}\right)_{\mathbb{F}_{q^{m}}}=\sum_{i=0}^{m-1}\mathscr{C}^{q^{i}}.$

###### Proof.

Take any $\boldsymbol{c}\in\mathscr{C}$. Then
$\textrm{Tr}\left(\boldsymbol{c}\right)=\boldsymbol{c}+\boldsymbol{c}^{q}+\cdots+\boldsymbol{c}^{q^{m-1}}$
also belongs to $\mathscr{C}+\mathscr{C}^{q}+\cdots+\mathscr{C}^{q^{m-1}}$.
This proves that
$\textrm{Tr}\left(\mathscr{C}\right)\subseteq\sum_{i=0}^{m-1}\mathscr{C}^{q^{i}}$
and therefore
$\textrm{Tr}\left(\mathscr{C}\right)_{\mathbb{F}_{q^{m}}}\subseteq\sum_{i=0}^{m-1}\mathscr{C}^{q^{i}}$.
On the other hand, let us prove that any $\mathscr{C}^{q^{i}}$ is a subspace
of $\textrm{Tr}\left(\mathscr{C}\right)_{\mathbb{F}_{q^{m}}}$ for any $i$.
Consider an arbitrary $\mathbb{F}_{q}$-basis
$\alpha\stackrel{{\scriptstyle\text{def}}}{{=}}\\{\alpha_{1},\cdots,\alpha_{m}\\}$
of $\mathbb{F}_{q^{m}}$. Let
${\boldsymbol{x}}_{i}\stackrel{{\scriptstyle\text{def}}}{{=}}\textrm{Tr}\left(\alpha_{i}\boldsymbol{c}\right)$.
Since

${\boldsymbol{x}}_{i}=\alpha_{i}\boldsymbol{c}+\alpha_{i}^{q}\boldsymbol{c}^{q}+\cdots+\alpha_{i}^{q^{m-1}}\boldsymbol{c}^{q^{m-1}}$

we have that

$\displaystyle\begin{pmatrix}{\boldsymbol{x}}_{1}&{\boldsymbol{x}}_{2}&\cdots&{\boldsymbol{x}}_{m}\end{pmatrix}$
$\displaystyle=$
$\displaystyle\begin{pmatrix}\boldsymbol{c}&\boldsymbol{c}^{q}&\cdots&\boldsymbol{c}^{q^{m-1}}\end{pmatrix}\underbrace{\begin{pmatrix}\alpha_{1}&\alpha_{2}&\cdots&\alpha_{m}\\\
\alpha_{1}^{q}&\alpha_{2}^{q}&\cdots&\alpha_{m}^{q}\\\
\vdots&\vdots&\vdots&\vdots\\\
\alpha_{1}^{q^{m-1}}&\alpha_{2}^{q^{m-1}}&\cdots&\alpha_{m}^{q^{m-1}}\end{pmatrix}}_{\stackrel{{\scriptstyle\text{def}}}{{=}}\boldsymbol{M}(\alpha)}$

$\boldsymbol{M}(\alpha)$ is the Moore matrix associated to
$\\{\alpha_{1},\cdots,\alpha_{m}\\}$ and is invertible because the
$\alpha_{i}$’s are linearly independent over $\mathbb{F}_{q}$. Therefore

$\begin{pmatrix}\boldsymbol{c}&\boldsymbol{c}^{q}&\cdots&\boldsymbol{c}^{q^{m-1}}\end{pmatrix}=\begin{pmatrix}{\boldsymbol{x}}_{1}&{\boldsymbol{x}}_{2}&\cdots&{\boldsymbol{x}}_{m}\end{pmatrix}\boldsymbol{M}(\alpha)^{-1}$

and therefore all the $\boldsymbol{c}^{q^{i}}$ are $\mathbb{F}_{q^{m}}$-linear
combinations of the ${\boldsymbol{x}}_{j}$’s and belong therefore to
$\textrm{Tr}\left(\mathscr{C}\right)_{\mathbb{F}_{q^{m}}}$. This shows that
$\mathscr{C}^{q^{i}}\subseteq\textrm{Tr}\left(\mathscr{C}\right)_{\mathbb{F}_{q^{m}}}$
for any $i$ and shows therefore the reverse inclusion

$\mathscr{C}+\mathscr{C}^{q}+\cdots+\mathscr{C}^{q^{m-1}}\subseteq\textrm{Tr}\left(\mathscr{C}\right)_{\mathbb{F}_{q^{m}}}.$

∎

##  Appendix B Proofs of Subsection 3.2

Let us recall the proposition we are going to prove. See 24

###### Proof.

Proof of (16). (16) was proved in [Ber00, Prop. 1].

Proof of (17).

Choose an $\mathbb{F}_{q}$-basis $\\{\alpha_{1},\cdots,\alpha_{m}\\}$ of
$\mathbb{F}_{q^{m}}$. We are first going to prove that

(39)
$\mathscr{G}({\boldsymbol{x}}_{\widecheck{i}},\Gamma)^{\perp}+\left\langle\,\mathbf{1}\,\right\rangle_{\mathbb{F}_{q}}=\mathscr{A}_{r}({\boldsymbol{x}}_{\widecheck{i}},i_{\widecheck{{\boldsymbol{y}}}}({\boldsymbol{x}}_{\widecheck{i}}-x_{i}))^{\perp}+\left\langle\,\mathbf{1}\,\right\rangle_{\mathbb{F}_{q}}.$
$\displaystyle\mathscr{A}_{r}({\boldsymbol{x}}_{\widecheck{i}},{\boldsymbol{y}}_{\widecheck{i}}({\boldsymbol{x}}_{\widecheck{i}}-x_{i}))^{\perp}$
$\displaystyle=\left\langle\,\textrm{Tr}\left(\alpha_{j}{\boldsymbol{x}}_{\widecheck{i}}^{a}({\boldsymbol{x}}_{\widecheck{i}}-x_{i}){\boldsymbol{y}}_{\widecheck{i}}\right)\mid
a\in\llbracket 0,r-1\rrbracket,j\in\llbracket
0,m-1\rrbracket\,\right\rangle_{\mathbb{F}_{q}}$
$\displaystyle=\left\langle\,\textrm{Tr}\left(\alpha_{j}{\boldsymbol{x}}_{\widecheck{i}}^{a+1}{\boldsymbol{y}}_{\widecheck{i}}\right)-\textrm{Tr}\left(\alpha_{j}x_{i}{\boldsymbol{x}}_{\widecheck{i}}^{a}{\boldsymbol{y}}_{\widecheck{i}}\right)\mid
a\in\llbracket 0,r-1\rrbracket,j\in\llbracket
0,m-1\rrbracket\,\right\rangle_{\mathbb{F}_{q}}$
$\displaystyle\subseteq\left\langle\,\textrm{Tr}\left(\alpha_{j}{\boldsymbol{x}}_{\widecheck{i}}^{b}{\boldsymbol{y}}_{\widecheck{i}}\right)\mid
b\in\llbracket 0,r\rrbracket,j\in\llbracket
0,m-1\rrbracket\,\right\rangle_{\mathbb{F}_{q}}$
$\displaystyle=\mathscr{A}_{r+1}({\boldsymbol{x}}_{\widecheck{i}},{\boldsymbol{y}}_{\widecheck{i}})^{\perp}$
$\displaystyle=\mathscr{G}({\boldsymbol{x}}_{\widecheck{i}},\Gamma)^{\perp}+\left\langle\,\mathbf{1}\,\right\rangle_{\mathbb{F}_{q}}$

On the other hand, since $\Gamma(x_{i})\neq 0$, then
$\Gamma({\boldsymbol{x}}_{\widecheck{i}})\not\in\left\langle\,{\boldsymbol{x}}_{\widecheck{i}}^{a}({\boldsymbol{x}}_{\widecheck{i}}-x_{i})\mid
a\in\llbracket 0,r-1\rrbracket\,\right\rangle_{\mathbb{F}_{q}}$. Therefore
$\left\langle\,\Gamma({\boldsymbol{x}}_{\widecheck{i}}),{\boldsymbol{x}}_{\widecheck{i}}^{a}({\boldsymbol{x}}_{\widecheck{i}}-x_{i})\mid
a\in\llbracket 0,r-1\rrbracket\,\right\rangle_{\mathbb{F}_{q}}$ is a vector
space of dimension $r+1$ of evaluations of polynomials with degree at most
$r$. Hence

$\left\langle\,\Gamma({\boldsymbol{x}}_{\widecheck{i}}),{\boldsymbol{x}}_{\widecheck{i}}^{a}({\boldsymbol{x}}_{\widecheck{i}}-x_{i})\mid
a\in\llbracket
0,r-1\rrbracket\,\right\rangle_{\mathbb{F}_{q}}=\left\langle\,{\boldsymbol{x}}_{\widecheck{i}}^{b}\mid
b\in\llbracket 0,r\rrbracket\,\right\rangle_{\mathbb{F}_{q}}.$

Since
$\textrm{Tr}\left(\alpha_{j}\Gamma({\boldsymbol{x}}_{\widecheck{i}}){\boldsymbol{y}}_{\widecheck{i}}\right)=\textrm{Tr}\left(\alpha_{j}\cdot\mathbf{1}\right)\in\left\langle\,\mathbf{1}\,\right\rangle_{\mathbb{F}_{q}}$,
we get

$\displaystyle\mathscr{G}({\boldsymbol{x}}_{\widecheck{i}},\Gamma)^{\perp}+\left\langle\,\mathbf{1}\,\right\rangle_{\mathbb{F}_{q}}$
$\displaystyle=\left\langle\,\textrm{Tr}\left(\alpha_{j}{\boldsymbol{x}}_{\widecheck{i}}^{b}{\boldsymbol{y}}_{\widecheck{i}}\right)\mid
b\in\llbracket 0,r\rrbracket,j\in\llbracket
0,m-1\rrbracket\,\right\rangle_{\mathbb{F}_{q}}$
$\displaystyle\subseteq\left\langle\,\textrm{Tr}\left(\alpha_{j}{\boldsymbol{x}}_{\widecheck{i}}^{a}({\boldsymbol{x}}_{\widecheck{i}}-x_{i}){\boldsymbol{y}}_{\widecheck{i}}\right)\mid
a\in\llbracket 0,r-1\rrbracket,j\in\llbracket
0,m-1\rrbracket\,\right\rangle_{\mathbb{F}_{q}}+\left\langle\,\mathbf{1}\,\right\rangle_{\mathbb{F}_{q}}$
$\displaystyle=\mathscr{A}_{r}({\boldsymbol{x}}_{\widecheck{i}},{\boldsymbol{y}}_{\widecheck{i}}({\boldsymbol{x}}_{\widecheck{i}}-x_{i}))^{\perp}+\left\langle\,\mathbf{1}\,\right\rangle_{\mathbb{F}_{q}}.$

Because of the last point,
$\mathbf{Sh}_{i}\left(\mathscr{A}_{r+1}({\boldsymbol{x}},{\boldsymbol{y}})^{\perp}\right)$
is the set of codewords of
$\mathscr{G}({\boldsymbol{x}},\Gamma)+\left\langle\,\mathbf{1}\,\right\rangle_{\mathbb{F}_{q}}$
which evaluate to $0$ at position $i$. Clearly the elements of
$\mathscr{A}_{r}({\boldsymbol{x}}_{\widecheck{i}},{\boldsymbol{y}}_{\widecheck{i}}({\boldsymbol{x}}_{\widecheck{i}}-x_{i}))^{\perp}$
viewed as polynomial evaluations and extended canonically at position $i$ as
the linear space

$\left\\{\textrm{Tr}\left({\boldsymbol{y}}({\boldsymbol{x}}-x_{i})P({\boldsymbol{x}})\right):\;P\in\mathbb{F}_{q^{m}}[X],\;\deg
P<r\right\\}$

belong to this set. Since the all one vector does not meet this property and
because of (39) this implies the point (17).

Proof of (18). This is just a consequence that
$\mathbf{Sh}_{i}\left(\mathbf{Sh}_{j}\left(\mathscr{C}\right)\right)=\mathbf{Sh}_{j}\left(\mathbf{Sh}_{i}\left(\mathscr{C}\right)\right)$
which holds for any code $\mathscr{C}$. Here we apply it to
$\mathscr{C}=\mathscr{A}_{r+1}({\boldsymbol{x}},{\boldsymbol{y}})^{\perp}$ and
apply the previous point:

$\displaystyle\mathbf{Sh}_{i}\left(\mathscr{A}_{r}({\boldsymbol{x}}_{\widecheck{j}},{\boldsymbol{y}}_{\widecheck{j}}({\boldsymbol{x}}_{\widecheck{j}}-x_{j}))^{\perp}\right)$
$\displaystyle=$
$\displaystyle\mathbf{Sh}_{i}\left(\mathbf{Sh}_{j}\left(\mathscr{A}_{r+1}({\boldsymbol{x}},{\boldsymbol{y}})^{\perp}\right)\right)\;\text{(by
\eqref{eq:shi})}$ $\displaystyle=$
$\displaystyle\mathbf{Sh}_{j}\left(\mathbf{Sh}_{i}\left(\mathscr{A}_{r+1}({\boldsymbol{x}},{\boldsymbol{y}})^{\perp}\right)\right)\;\;\text{(by
the previous remark)}$ $\displaystyle=$
$\displaystyle\mathbf{Sh}_{j}\left(\mathscr{A}_{r}({\boldsymbol{x}}_{\widecheck{i}},{\boldsymbol{y}}_{\widecheck{i}}({\boldsymbol{x}}_{\widecheck{i}}-x_{i}))^{\perp}\right)\text{(by
\eqref{eq:shi})}$

∎