11institutetext: Tampere University, Finland. 11email: (tanveer.khan,
fahad.sohrab, antonios.michalas<EMAIL_ADDRESS>
# Trustworthiness of $\mathbb{X}$ Users: A One-Class Classification Approach

Tanveer Khan The first two authors contributed equally to this work. Fahad
Sohrab  Antonis Michalas  Moncef Gabbouj

###### Abstract

$\mathbb{X}$ (formerly Twitter) is a prominent online social media platform
that plays an important role in sharing information making the content
generated on this platform a valuable source of information. Ensuring trust on
$\mathbb{X}$ is essential to determine the user credibility and prevents
issues across various domains. While assigning credibility to $\mathbb{X}$
users and classifying them as trusted or untrusted is commonly carried out
using traditional machine learning models, there is limited exploration about
the use of One-Class Classification (OCC) models for this purpose. In this
study, we use various OCC models for $\mathbb{X}$ user classification.
Additionally, we propose using a subspace-learning-based approach that
simultaneously optimizes both the subspace and data description for OCC. We
also introduce a novel regularization term for Subspace Support Vector Data
Description (SSVDD), expressing data concentration in a lower-dimensional
subspace that captures diverse graph structures. Experimental results show
superior performance of the introduced regularization term for SSVDD compared
to baseline models and state-of-the-art techniques for $\mathbb{X}$ user
classification.

##  1 Introduction

Online Social Networks (OSNs) have become an essential tool for modern
communication, enabling people to interact, while spending significant time on
these platforms. It is now becoming an integral part of our lives, and people
are using it for different purposes, including connection with friends and
family, participation in online communities, brand promotion, finding and
sharing information, and much more gazi2017research . The most popular OSNs
include Facebook, $\mathbb{X}$, Instagram, and LinkedIn. This work focuses on
$\mathbb{X}$ – an OSN platform that allows users to share and discover short
messages or tweets limited to 280 characters. $\mathbb{X}$ has 310 million
active users publishing 500 million tweets per day das2019much . Also,
$\mathbb{X}$ has become a valuable tool enabling users to share information
with a wide audience quickly and easily. It allows users to see tweets
relevant to their interests, retweet or like other users’ tweets, or post
their own tweets. While this makes it easy for $\mathbb{X}$ users to share
updates and information with their followers in real-time, it also makes it
easier for fake account users to carry out malicious activities such as
sharing unverified information vosoughi2018spread . Additionally, it has been
observed that fake news spreads more rapidly on $\mathbb{X}$ than real news,
damaging the reputation and reliability of the $\mathbb{X}$. Various
techniques have been proposed khan2021fake  to tackle the spread of false
information, with one approach being the classification of $\mathbb{X}$ users
as trusted or untrusted zhang2018social . This classification is of
significant importance in maintaining the reputation and reliability of the
$\mathbb{X}$ platform. For example, identifying a trusted and reliable
$\mathbb{X}$ user ensures the continued success and usefulness of the
$\mathbb{X}$ platform as a trusted and valuable social media tool.

There are various ways for $\mathbb{X}$ user classification such as using
Machine Learning (ML) pritzkau2021finding , and Natural Language Processing
(NLP) devarajan2023ai . Among these, ML models have been widely used in
various research to classify $\mathbb{X}$ users into different categories
based on their profiles, activity, and content of the tweets. The process
involves collecting and preprocessing large amounts of data, including user
profiles and tweets, and then training an ML model to classify users into
different categories based on the available features. The model can then be
used to classify new, unseen users. The ML algorithms used for $\mathbb{X}$
user classification are supervised asfand2023classifying , unsupervised
ahmad2020information , and semi-supervised khan2020trust ; khan2021seeing .
Classifying $\mathbb{X}$ users as trusted or untrusted using only ML models
can be challenging due to high-dimensional and variable characteristics of big
data wang2020survey . Despite the curse of dimensionality and the imbalanced
nature of the data, the appropriate techniques and models hold the potential
to address these challenges successfully. In our approach, we rely on OCC
models, where the decision function is inferred using training data from a
single class only. It is used when a large amount of data is available for the
class of interest but little or no data is available for other classes
alam2020one . OCC differs from traditional binary classification models, which
are trained using data from both categories. We use a manually labeled dataset
obtained from Khan et al. khan2020trust  research, which involved gathering
data for 50,000 $\mathbb{X}$ users, with manual labeling for 1,000 of them. By
applying different OCC models to the labeled dataset, our goal is to answer
the following research questions (RQs):

RQ 1: How effective is the OCC in accurately identifying political
$\mathbb{X}$ users as trusted or untrusted, and what are the comparative
strengths and weaknesses among different OCC models in this context?

RQ 2: What are the key challenges OCC faces when classifying political users
on $\mathbb{X}$, and can the performance of OCC be optimized for political
user identification through subspace learning for OCC?

RQ 3: Can we encode the relationships between the training data points in a
lower-dimensional subspace optimized for OCC while capturing and preserving
the local structure of target class data?

Contributions: The main contributions of this work can be summarized as
follows:

  1. bx1.

We propose using subspace-learning-based OCC for $\mathbb{X}$ user
identification.

  2. bx2.

We propose a novel regularizer for Subspace Support Vector Data Description
(SSVDD) expressing the concentration of the data in a lower-dimensional
subspace that captures different graph structures.

  3. bx3.

In the proposed regularization term, any suitable graph can be used to encode
the corresponding graph structure, and we evaluate its effectiveness by
comparing it with different OCC models.

###  1.1 Organization

The rest of the paper is organized as follows. In section 2, we provide
necessary background information about different OCC models. In section 3, we
provide important published works in the area of $\mathbb{X}$ user
credibility, accompanied by a detailed discussion of our proposed approach in
section 4. The data collection and experimental results are presented in
section 5. Finally, we conclude the paper in section 6.

##  2 Preliminaries

In ML, OCC refers to an approach to building a model by considering data from
a single class only. OCC is appropriate for scenarios where it is critical to
identify one of the categories, but the examples from that specific category
are scarce or statistically so diverse that they cannot be used during the
training process. OCC has found application in different areas, such as early
detection of myocardial infection degerli2022early , rare insect
classification sohrab2020boosting , and credit card fraud detection
zaffar2023credit . These applications present data scarcity challenges from
one of the categories to be modeled.

Among the widely-used OCC approaches, One-class Support Vector Machine (OCSVM)
and Support Vector Data Description (SVDD) have been proven as powerful data
description methods over time. These methods identify the so-called support
vectors as crucial for determining the decision boundary. In OCSVM, a
hyperplane is created to separate the target class in a way that maximizes the
distance of the hyperplane from the origin scholkopfu2000sv . The
classification of a new data point is determined by its location relative to
the hyperplane: if it falls on the positive side, it is considered normal;
otherwise, it is flagged as abnormal. SVDD, on the other hand, creates a
hyperspherical boundary around the target class data within the original
feature space by minimizing the volume of the hypersphere.

Let us denote the target class training samples to be encapsulated inside a
hypersphere by a matrix
$\mathbf{X}=[\mathbf{x}_{1},\mathbf{x}_{2},\dots,\mathbf{x}_{N}],\mathbf{x}_{i}\in\mathbb{R}^{D}$,
where $N$ is the number of samples and $D$ is dimensionality of data. The
formulation of SVDD is expressed as follows:

$\displaystyle\centering\min\quad
F(R,\mathbf{a})=R^{2}+C\sum_{i=1}^{N}\xi_{i}\ \ \
\textrm{s.t.}\quad\|\mathbf{x}_{i}-\mathbf{a}\|_{2}^{2}\leq
R^{2}+\xi_{i},\quad\xi_{i}\geq 0,\>\>\forall
i\in\\{1,\dots,N\\},\@add@centering$ (1)

where $R$ represents the radius, $\mathbf{a}\in\mathbb{R}^{D}$ is the center
of the hypersphere, and slack variables $\xi_{i},i=1,\dots,N$ are introduced
to enable the possibility of target data being outliers. The hyperparameter
$C>0$ controls the trade-off between the volume of the hypersphere and the
presence of data points outside the hypersphere. A test sample is assigned to
the positive class if its distance from the center of the hypersphere is equal
to or less than the radius $R$.

A distinct category in OCC, Graph Embedded One-Class Classifiers, refers to
methods that integrate generic graph structures expressing relevant geometric
relationships in their optimization processes. Graph Embedded One-Class
Support Vector Machine (GEOCSVM) is an example that incorporates graph-based
information and enhances the traditional OCSVM approach. By leveraging graph
information, GEOCSVM compares favorably to the standard OCSVM. In GEOCSVM, the
relationship between training patterns can be described locally and globally
using a single graph or a combination of fully connected and kNN graphs
mygdalis2016graph . Similarly, Graph Embedded Support Vector Data Description
(GESVDD) is a type of OCC that combines the SVDD approach with graph-based
information. In GESVDD, the graph-based information is incorporated into the
optimization process of the SVDD. Like SVDD, GESVDD also creates a hypersphere
around the target class data to separate the target class data from the
outliers in an OCC problem. However, graph-based information in GESVDD
provides additional information that can help to improve the separation of
target class data from outliers mygdalis2016graph . Other extensions of graph-
based OCC include Graph Embedded Subspace Support Vector Data Description
(GESSVDD) sohrab2023graph  that poses the subspace learning for OCC as a graph
embedding problem.

Traditional boundary-based OCC methods primarily find a data description in
the given feature space. However, a contemporary paradigm shift is evident in
the form of subspace learning-based techniques that not only form a data
description but also optimize a subspace simultaneously. A leading technique
in this paradigm is the SSVDD sohrab2018subspace , which defines a data
description along with data mapping to low-dimensional feature space optimized
for OCC. To define a concise representation of the target class, the method
repeatedly optimizes data mapping and data description. The optimization
function of SSVDD is as follows:

$\displaystyle\centering\min\quad
F(R,\mathbf{a})=R^{2}+C\sum_{i=1}^{N}\xi_{i}\ \ \
\textrm{s.t.}\quad\|\mathbf{Qx}_{i}-\mathbf{a}\|_{2}^{2}\leq
R^{2}+\xi_{i},\quad\xi_{i}\geq 0,\>\>\forall
i\in\\{1,\dots,N\\},\@add@centering$ (2)

where $\mathbf{Q}\in\mathbb{R}^{d\times D}$ is the projection matrix for
mapping the data from the original D-dimensional feature space to an optimized
lower d-dimensional space. In SSVDD, an augmented version of the Lagrangian
with a regularization term $\psi$ is optimized:

$L=\sum_{i=1}^{N}\alpha_{i}\mathbf{x}_{i}^{\intercal}\mathbf{Q}^{\intercal}\mathbf{Q}\mathbf{x}_{i}-\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_{i}\mathbf{x}_{i}^{\intercal}\mathbf{Q}^{\intercal}\mathbf{Q}\mathbf{x}_{j}\alpha_{j}+\beta\psi,$
(3)

where $\alpha$ represents the Lagrange multipliers, and $\beta$ is used to
control the importance of the regularization term. The regularization term
$\psi$ expresses the class variance in the $d$-dimensional space and it is
denoted as

$\psi=\text{Tr}(\mathbf{Q}\mathbf{X}\boldsymbol{\lambda}\boldsymbol{\lambda}^{\intercal}\mathbf{X}^{\intercal}\mathbf{Q}^{\intercal}),$
(4)

where Tr($\cdot$) is the trace operator and $\lambda\in\mathbb{R}^{N}$ is a
vector used to select the contribution of certain data points in the
optimization process, leading to different variants of SSVDD. The different
variants are as follows.

  * •

SSVDD$\psi 1$: In this variant, the regularization term becomes obsolete and
is not used during the data description.

  * •

SSVDD$\psi 2$: In this case, all the training samples describe the class
variance in the regularization term.

  * •

SSVDD$\psi 3$: In this case, the samples belonging to the boundary and outside
the boundary are used in the regularization term.

  * •

SSVDD$\psi 4$: In this variant, only the support vectors that belong to the
class boundary are used to describe the class variance in the regularization
term.

The selection of different data instances in the regularization term is
carried out by replacing the $\lambda$ value accordingly with the $\alpha$
values. The updating of the projection matrix $\mathbf{Q}$ is carried out by
utilizing the gradient of (3), expressed as:

$\displaystyle\mathbf{Q}\leftarrow\mathbf{Q}-\eta\Delta L.$ (5)

Here, $\eta$ denotes the learning rate parameter. This work primarily focuses
on subspace learning-based OCC and proposes a graph-based regularization for
SSVDD.

##  3 Related Work

A lot of research has looked into different aspects of $\mathbb{X}$, such as
bot detection, analysis of the spread of fake news, and assessing the
credibility of $\mathbb{X}$ users. Bots can be helpful for tasks such as
posting information about news and providing assistance during emergencies,
etc haustein2016tweets , but some bots can be used for malicious purposes such
as influencing public opinion or spreading malware fu2018combating . Hence,
identifying bots is vital for $\mathbb{X}$ to enforce its platform terms and
conditions. Hence, researchers have proposed different methods
rodriguez2020one  to create accurate models for bot detection.

Apart from bot detection, another important area of research is the detection
of fake news, which is rampant – tends to be retweeted faster than true ones
meyers2020fake . Various ML models, particularly of the supervised
classification, have been used for fake news detection faustini2020fake . For
example, Hassan et al. hassan2017toward  extracted features from the sentences
and used a support vector machine to detect fake news. Despite the popularity
of the topic there has been limited progress in fake news detection. This is
partly due to the ongoing controversy surrounding the term ‘fake news’ and the
lack of a universally accepted definition thereof meyers2020fake .
Nevertheless, several works have delved into fake news detection by assessing
the credibility of tweets or classifying the $\mathbb{X}$ users as trusted or
untrusted. Another study proposes an automated ranking technique to evaluate
tweet credibility. Gupta et al. worked on assigning a credibility score to
each tweet. Another interesting work in this domain is the work conducted by
Tanveer et al. khan2020trust ; khan2021seeing , presented a model that
analyzes $\mathbb{X}$ users, assigning a score to each user based on their
social profile, tweet credibility, and h-index score. While there has been
considerable research in this domain, it is important to note that only a
limited number of studies utilize an OCC to classify $\mathbb{X}$ user as
trusted or untrusted. This underscores a critical gap in the existing body of
knowledge. Adopting OCC becomes particularly valuable when the task involves
identifying a specific category with limited or diverse training instances.

##  4 Methodology

This research aims to develop a regularization strategy for training OCC
models, specifically tailored for identifying political $\mathbb{X}$ users,
categorizing them as either trusted or untrusted, as shown in Figure 1. For
this reason, we use the manually labeled dataset of 1000 political
$\mathbb{X}$ users from the paper khan2020trust . For each user, a unique
profile is created, containing various features. Some are basic features
extracted for each $\mathbb{X}$ user linked to their account. More
specifically, these features are  (i) Number of friends,  (ii) Number of
followers,  (iii) Number of retweets,  (iv) Number of likes,  (v) URLs,  (vi)
Lists,  (vii) Status and  (viii) Mention by others.

The basic features are used to calculate more advanced features like a social
reputation score, an h-index score, a sentiment score, and tweet credibility.
Below, we provide a brief description of these advanced features:

  * •

Social reputation score: It provides the number of users interested in the
updates of an $\mathbb{X}$ user.

  * •

H-index score: The h-index is used to measure how impactful an $\mathbb{X}$
user is. This is measured by considering the number of likes and retweets of a
$\mathbb{X}$ user.

  * •

Sentiment score: The tweets of a $\mathbb{X}$ user are classified as positive,
negative, and neutral, based on which sentiment score is assigned to each
$\mathbb{X}$ user.

  * •

Tweet credibility: It is calculated by considering the retweet ratio, liked
ratio, URL ratio, user hashtag ratio, and original content ratio.

  * •

Influence score: The influence score of a $\mathbb{X}$ user is calculated by
considering the social reputation, h-index score, sentiment score, and tweet
credibility.

Details on calculating influence scores from basic features and using advanced
features are beyond this paper’s scope. For more information, refer to the
previous article on this topic khan2020trust . All political $\mathbb{X}$
users are classified as trusted or untrusted based on social reputation, tweet
credibility, sentiment score, h-index score, and influence score. All
$\mathbb{X}$ accounts with abusive and harassing tweets, a low social
reputation, h-index, and influence score are grouped as untrusted users, while
those who are more reputable among users with a high h-index score, more
credible tweets and a high influence score are grouped as trusted users.

Having a dataset for political $\mathbb{X}$ users as either trusted or
untrusted based on various criteria, we then focus on inferring a model based
on using information only from trusted users. We train different OCC models,
including SVDD, ESVDD, OCSVM, SSVDDr$\psi_{1}$, SSVDDr$\psi_{2}$,
SSVDDr$\psi_{3}$, SSVDDr$\psi_{4}$ GEOCSVM and GESVDD. We also propose a novel
regularization term for SSVDD. The newly proposed regularization term
considers the graph information, which measures the concentration of the data
in a lower-dimensional subspace and captures the essential features of the
training set while preserving the local structure of the data. The proposed
regularization term is defined as

$\gamma=\text{Tr}(\mathbf{Q}\mathbf{X}\mathbf{L}_{x}\mathbf{X}^{\intercal}\mathbf{Q}^{\intercal}),$
(6)

where $\mathbf{L}_{x}$ is the Laplacian matrix of the graph. The subscript $x$
denotes the adopted graph type. The Laplacian is defined as

$\displaystyle\mathbf{L}_{x}=\mathbf{D}_{x}-\mathbf{A}_{x},\;\;\;[\mathbf{D}_{x}]_{ii}=\sum_{j\neq
i}[\mathbf{A}_{x}]_{ij},\forall i\in\\{1,\dots,N\\},$ (7)

where $\mathbf{D}_{x}$ is the degree matrix and
$\mathbf{A}_{x}\in\mathbb{R}^{N\times N}$ serves as the graph’s weight matrix.
In what follows, we drop the subscript X for notation simplicity.

We investigated the three different graph Laplacians in the proposed
regularization term $\gamma$. In the first experiment, we exploit the local
geometric information by employing k-Nearest Neighbor (kNN) and setting the
Laplacian matrix to

$\mathbf{L}_{kNN}=\mathbf{D}_{kNN}-\mathbf{A}_{kNN},$ (8)

where $[\mathbf{A}_{kNN}]_{ij}=1,$ if $\mathbf{x}_{i}\in\mathcal{N}_{j}$ or
$\mathbf{x}_{j}\in\mathcal{N}_{i}$ and 0, otherwise. $\mathcal{N}_{i}$ denotes
the nearest neighbors of $\mathbf{x}_{i}$. Adjusting the $k$ numbers of
neighbors in kNN allows the neighborhoods $\mathcal{N}_{i}$ to be defined
accordingly. In the second experiment, we use within-cluster Laplacian
information.

$\mathbf{L}_{w}=\mathbf{I}-\sum_{c=1}^{\mathcal{C}}\frac{1}{N_{c}}\mathbf{1}_{c}\mathbf{1}_{c}^{T},$
(9)

where $\mathbf{I}$ is an identity matrix, $\mathcal{C}$ denotes the total
numbers of clusters, $\mathbf{1}$ is a vector of ones, $N_{c}$ is the total
number of instances belonging to cluster $c$ and $\mathbf{1}_{c}$ represents a
vector with ones corresponding to instances that belong to cluster $c$ and
zeros elsewhere. In the third experiment, we use the between-cluster scatter
information:

$\mathbf{L}_{b}=\sum_{c=1}^{\mathcal{C}}N_{c}\left(\frac{1}{N_{c}}\mathbf{1}_{c}-\frac{1}{N}\mathbf{1}\right)\left(\frac{1}{N_{c}}\mathbf{1}_{c}-\frac{1}{N}\mathbf{1}^{T}\right).$
(10)

In this paper, we denote the three variants of the proposed regularization
strategies for SSVDD as SSVDD$\gamma L_{kNN}$, SSVDD$\gamma L_{w}$, and
SSVDD$\gamma L_{b}$, respectively. For non-linear data description, we
employed non-linear projection trick (NPT) kwak2013nonlinear . NPT is
equivalent to employing the widely recognized kernel trick while enabling the
use of the method’s linear variant.The kernel matrix is obtained as

$\mathbf{K}_{ij}=\exp\left(\frac{-\|\mathbf{x}_{i}-\mathbf{x}_{j}\|_{2}^{2}}{2\sigma^{2}}\right),$
(11)

where $\sigma$ is a hyperparameter scaling the distance between
$\mathbf{x}_{i}$ and $\mathbf{x}_{j}$. We followed similar steps for non-
linear data description as adapted in recent variants and extensions of SSVDD
sohrab2020ellipsoidal ; sohrab2023newton .

Figure 1: One-class classification categorizes $\mathbb{X}$ platform users as
trusted or untrusted

##  5 Experimental Results and Model Evaluation

To extract the features from $\mathbb{X}$ and generate the dataset, we used
Python 3.5. The Python script was executed locally on a machine with the
following configuration: Intel Core i7, 2.80*8 GHZ, 32GB, Ubuntu 16.04 LTS 64
bit. For the training and evaluation of the OCC models, we switched to Matlab
and performed the experiments on Intel(R) Xeon(R) CPU E5-2650 v3 2.30GHz 64GB
RAM. We provide the open-source implementation of our work on
Github111https://github.com/fahadsohrab/xssvdd.

A comprehensive set of evaluating metrics is reported over the test set to
compare different OCC models. Accuracy (Accu) provides the ratio of correctly
classified instances to the total number of instances, True Positive Rate
(TPR) represents the proportion of positive instances correctly classified,
while True Negative Rate (TNR) indicates the ratio of true negatives to the
total number of negative samples. Precision (Pre) measures the proportion of
instances classified as positive that are truly positive, and the F1-score is
defined as the harmonic mean of precision and TPR. Additionally, Geometric
Mean is employed to discern the best-performing parameters on training set,
calculated as square root of product of TPR and TNR.

###  5.1 Preprocessing the data

In this work, we chose to analyze the $\mathbb{X}$ account of 1,000
politicians 222https://zenodo.org/records/7014109 and the main reason for
evaluating the profiles of politicians is their intrinsic potential to
influence public opinion as their content originates and exists in a sphere of
political life, which is, unfortunately, often surrounded by controversial
events and outcomes. We selected 70 percent of the data for training and 30
percent for testing. The train and test sets are randomly selected by keeping
the proportions of the two classes similar to the collected dataset. We
perform the random selection five times; hence, we use five different train-
test sets for the experiments to check the robustness of the OCC methods. We
normalize the data by subtracting the mean and dividing it by the Standard
Deviation (STD). These are both computed using only the target class samples
from the training set. During the training, a 5-fold cross-validation
technique is used over the training set to select the hyperparameters of the
models. More details on the hyperparameters can be found in the GitHub.

###  5.2 Results and discussions

In Table 1, we report the average performance measures of various OCC methods
on the five data splits of the dataset. The classifiers are divided into two
categories: linear OCC and non-linear OCC. In Table 1, we also report the STD
of evaluating metrics for the linear and non-linear methods over the five data
splits of the dataset.

Considering the GM values, the linear OCC generally have lower performance
measures than non-linear OCC. This indicates that non-linear OCC are more
adept at correctly predicting both positive and negative classes than linear
OCC. For example, in non-linear OCC, SSVDD$\gamma L_{kNN}$ achieves the
highest GM value, which is 0.80, surpassing the 0.64 obtained by SSVDD$\gamma
L_{w}$, a linear OCC. Conversely, non-linear SSVDD$\psi 1$ OCC achieve the
lowest GM value which is 0.43, as opposed to 0.19 recorded by ESVDD linear
OCC.

Regarding Accu, most non-linear OCC models consistently outperform their
linear counterparts. As shown in Table 1, the highest Accu, reaching 0.80, is
achieved by non-linear OCC SSVDD$\gamma L_{kNN}$. In contrast, three linear
OCC models – SSVDD$\gamma L_{w}$, SSVDD$\gamma L_{b}$ and SSVDD$\gamma
L_{kNN}$ – received a slightly lower Accu of 0.74. The lowest Accu among non-
linear OCC models is 0.48, attributed to OCSVM, while the linear OCSVM
achieves 0.44. For the other evaluation metrics, Pre and F1 remain stable,
while TPR consistently remains high, indicating the model’s effectiveness in
identifying positive instances.

To summarize, linear OCSVM has the lowest Accu (0.44) and F1-score (0.41)
among all classifiers, while SVDD and ESVDD have very low TNR and GM values in
linear cases. Linear SSVDD classifiers with regularization terms $\psi 1$ and
$\psi 4$ have similar performance measures and are somewhat better than OCSVM,
SVDD, and ESVDD. GEOCSVM has the highest Accu (0.78) and GM (0.78) scores,
indicating its superior performance in identifying positive and negative
instances.

The superior performance of non-linear OCC models in terms of GM and Accu can
be attributed to the inherent complexity of the data distribution. Non-linear
classifiers are more flexible in capturing intricate relationships and
patterns within the data, especially when the decision boundary is non-linear.

Examining the SSVDD variants and their performance metric, GM, concerning the
regularization term $\psi$, reveals that $\psi 3$ yields the most favorable
outcomes for both linear and non-linear classifiers followed closely by $\psi
2$, then $\psi 1$, with $\psi 4$ performing the least effectively. The
superiority of SSVDD$\psi 3$ can be attributed to its consideration of samples
inside and outside the class boundary during the training in the
regularization term, providing a more comprehensive understanding of the class
variance. Conversely, SSVDD$\psi 4$ performs poorly as it only considers
support vectors on the class boundary in the regularization term, potentially
missing crucial information about class distribution.

Table 1: Measuring the performance of linear and non-linear OCC models averaged over five test splits with ± STD | Accu | TPR | TNR | Pre | F1 | GM
---|---|---|---|---|---|---
| Linear OCC
SSVDD$\psi 1$ | 0.68 ± 0.02 |  0.98 ± 0.01 | 0.27 ± 0.05 | 0.65 ± 0.01 | 0.78 ± 0.01 | 0.51 ± 0.05
SSVDD$\psi 2$ | 0.69 ± 0.03 | 0.97 ± 0.02 | 0.31 ± 0.07 | 0.66 ± 0.02 | 0.78 ± 0.02 | 0.54 ± 0.06
SSVDD$\psi 3$ | 0.73 ± 0.06 | 0.97 ± 0.02 | 0.41 ± 0.16 | 0.70 ± 0.06 | 0.81 ± 0.03 | 0.62 ± 0.12
SSVDD$\psi 4$ | 0.69 ± 0.03 |  0.98 ± 0.01 | 0.29 ± 0.08 | 0.66 ± 0.02 | 0.79 ± 0.02 | 0.53 ± 0.07
OCSVM | 0.44 ± 0.10 | 0.34 ± 0.10 | 0.59 ± 0.36 | 0.59 ± 0.13 | 0.41 ± 0.04 | 0.39 ± 0.16
SVDD | 0.58 ± 0.01 | 0.96 ± 0.01 | 0.05 ± 0.03 | 0.59 ± 0.01 | 0.73 ± 0.00 | 0.22 ± 0.06
ESVDD | 0.57 ± 0.01 | 0.96 ± 0.02 | 0.04 ± 0.02 | 0.58 ± 0.00 | 0.72 ± 0.01 | 0.19 ± 0.06
SSVDD$\gamma L_{kNN}$ | 0.74 ± 0.04 | 0.97 ± 0.01 | 0.41 ± 0.12 | 0.70 ± 0.04 | 0.81 ± 0.02 | 0.63 ± 0.09
SSVDD$\gamma L_{b}$ | 0.74 ± 0.07 |  0.98 ± 0.01 | 0.42 ± 0.19 | 0.71 ± 0.07 |  0.82 ± 0.04 | 0.63 ± 0.14
SSVDD$\gamma L_{w}$ | 0.74 ± 0.02 | 0.97 ± 0.01 | 0.42 ± 0.04 | 0.70 ± 0.02 | 0.81 ± 0.01 | 0.64 ± 0.03
| Non-Linear OCC
SSVDD$\psi 1$ | 0.66 ± 0.09 | 0.88 ± 0.15 | 0.35 ± 0.39 | 0.68 ± 0.12 | 0.75 ± 0.04 | 0.43 ± 0.31
SSVDD$\psi 2$ | 0.70 ± 0.08 | 0.80 ± 0.16 | 0.55 ± 0.35 | 0.75 ± 0.14 | 0.75 ± 0.04 | 0.61 ± 0.19
SSVDD$\psi 3$ | 0.74 ± 0.09 | 0.80 ± 0.11 | 0.67 ± 0.31 | 0.80 ± 0.12 | 0.79 ± 0.06 | 0.70 ± 0.20
SSVDD$\psi 4$ | 0.65 ± 0.09 | 0.85 ± 0.19 | 0.36 ± 0.41 | 0.69 ± 0.13 | 0.73 ± 0.06 | 0.40 ± 0.33
OCSVM | 0.48 ± 0.04 | 0.53 ± 0.04 | 0.40 ± 0.12 | 0.56 ± 0.04 | 0.54 ± 0.02 | 0.45 ± 0.06
SVDD | 0.71 ± 0.12 | 0.84 ± 0.11 | 0.53 ± 0.43 | 0.76 ± 0.16 | 0.78 ± 0.05 | 0.56 ± 0.34
ESVDD | 0.56 ± 0.02 | 0.58 ± 0.17 | 0.54 ± 0.26 | 0.66 ± 0.09 | 0.60 ± 0.07 | 0.52 ± 0.04
GEOCSVM | 0.78 ± 0.02 | 0.74 ± 0.06 | 0.83 ± 0.06 | 0.86 ± 0.03 | 0.79 ± 0.03 | 0.78 ± 0.01
GESVDD | 0.70 ± 0.12 | 0.61 ± 0.27 | 0.84 ± 0.13 | 0.87 ± 0.09 | 0.67 ± 0.24 | 0.68 ± 0.17
SSVDD$\gamma L_{kNN}$ |  0.80 ± 0.05 | 0.76 ± 0.11 |  0.85 ± 0.08 |  0.88 ± 0.05 | 0.81 ± 0.06 |  0.80 ± 0.05
SSVDD$\gamma L_{b}$ | 0.73 ± 0.09 | 0.77 ± 0.10 | 0.68 ± 0.21 | 0.78 ± 0.10 | 0.77 ± 0.07 | 0.71 ± 0.12
SSVDD$\gamma L_{w}$ | 0.78 ± 0.02 | 0.84 ± 0.07 | 0.70 ± 0.08 | 0.80 ± 0.03 |  0.82 ± 0.03 | 0.76 ± 0.02

The best results for linear and non-linear OCC models are obtained by
appending our new regularization term $\gamma$ to SSVDD (see Table 1). The
performance of all three linear OCC models, namely: SSVDD$\gamma L_{kNN}$,
SSVDD$\gamma L_{b}$ and SSVDD$\gamma L_{w}$, is nearly identical, bearing
limited impact on performance metrics. On the other hand, among the non-linear
OCC models, SSVDD$\gamma L_{kNN}$ demonstrates superior performance,
outperforming the other two counterparts, namely SSVDD$\gamma L_{w}$ and
SSVDD$\gamma L_{b}$, where the latter ranks the lowest in performance.

Additional information about the use of $\gamma$ for SSVDD and its impact on
performance metric can be found in Figure 2 (a) for linear classification
using kNN, and in Figure 2 (b) for non-linear classifiers. Looking at the
linear OCC models in Figure 2 (a), the GM value remains steady at 0.57 to
0.63, and Accu falls within the range of 0.70 to 0.74 across various values of
k for kNN, showing a stable performance level. All the performance metrics
show stability, except TNR fluctuates, which tend to be on the lower side.
Unlike the stable results in the linear classifier, the non-linear classifier
shows a distinct pattern (see Figure 2 (b)). The non-linear OCC displays
variable performance, with GM values from 0.54 to 0.80 and Accu ranging from
0.67 to 0.80.

We also present the performance metrics for linear and non-linear SSVDD with
the proposed regularization term $\gamma$, focusing on the between-cluster
scatter Laplacian ($L_{b}$). As can be seen in Figure 2 (c), and Figure 2 (d),
the choice of hyperparameter $\mathcal{C}$ in $L_{b}$ significantly impacts
the performance of both linear and non-linear OCC models. The linear OCC
models show varied performance across different values of $\mathcal{C}$ for
$L_{b}$. For example, Accu ranges from 0.61 to 0.74, with the highest
performance achieved at $L_{b=4}$, while precision falls within the range of
0.61 to 0.71. TPR fluctuates between 0.96 and 0.98, showing a reliable
identification of positive instances. GM and TNR show a similar pattern, both
displaying lower values. In contrast, non-linear OCC models show distinct
behavior, with TPR at the top, varying between 0.66 and 0.86, followed by
F1-score and Accu, both of which show a stable performance. However, GM and
TNR, position at the last, show high variation.

Figure 2: Evaluating SSVDD performance with the proposed regularization term
$\gamma$, varying k for kNN, and different cluster values ($\mathcal{C}$) for
$L_{b}$ and $L_{w}$.

Following, we will analyze the results for within-cluster Laplacian ($L_{w}$).
As can be seen in Figure 2 (e), linear classifiers show varying performance
across different $\mathcal{C}$ values for $L_{w}$. Accu ranges from 0.64 to
0.74 (at $L_{w}=7$), and TPR fluctuates between 0.96 and 0.98, indicating a
consistent ability to identify positive instances correctly. Precision ranges
from 0.65 to 0.70, and GM shows variations but generally remains between 0.56
and 0.64. The non-linear classifiers in Figure 2 (f), show different behavior,
with Accu ranging from 0.68 to 0.78. TPR varies between 0.73 and 0.89 and
precision fluctuates between 0.71 and 0.81. It is noteworthy that at
$L_{w}=3$, the non-linear OCC models achieve their highest F1-score and GM
value.

##  6 Conclusion

Considering the significant impact of information sharing on social media,
specifically on platform $\mathbf{X}$, our goal was to identify the trusted or
untrusted $\mathbf{X}$ users. Our study provided insights into the
effectiveness of OCC models in classifying political users on platform
$\mathbf{X}$, through exploring OCC models. In addition, it included a novel
regularization term for SSVDD.

In response to the research questions RQ 1-3, our findings demonstrate the
effectiveness of OCC models in identifying political $\mathbf{X}$ users as
trusted or untrusted. The results consistently demonstrate that non-linear OCC
classifiers outperform their linear counterparts. This paper provided brief
insights on the recent improvements in OCC, notably the new paradigm of
subspace learning for SVDD used to tackle the curse of dimensionality. Our
study confirmed the potential of OCC performance optimization for political
user identification through subspace learning. The proposed subspace-learning-
based approach, particularly with the introduced regularization term for
SSVDD, showcased superior performance compared to baseline models.

In the future, we will explore alternative kernel types and graph structures
to enhance the performance further. Additionally, we aim to adapt the proposed
regularization term to the Multi-modal Subspace Support Vector Data
Description sohrab2021multimodal  framework and analyze its effectiveness over
other application domains.

## References

  * [1] Mehmet Ali Gazi, Muharrem Çetin, and ÇAKI Caner.  The research of the level of social media addiction of university students.  International Journal of Social Sciences and Education Research, 3(2):549–559, 2017.
  * [2] Rajkumar Das, Gour Karmakar, and Joarder Kamruzzaman.  How much i can rely on you: Measuring trustworthiness of a twitter user.  IEEE Transactions on Dependable and Secure Computing, 18(2):949–966, 2019.
  * [3] Soroush Vosoughi, Deb Roy, and Sinan Aral.  The spread of true and false news online.  science, 359(6380):1146–1151, 2018.
  * [4] Tanveer Khan, Antonis Michalas, and Adnan Akhunzada.  Fake news outbreak 2021: Can we stop the viral spread?  Journal of Network and Computer Applications, 190:103112, 2021.
  * [5] Zhiyong Zhang and Brij B Gupta.  Social media security and trustworthiness: overview and new direction.  Future Generation Computer Systems, 86:914–925, 2018.
  * [6] Albert Pritzkau, Steffen Winandy, and Theresa Krumbiegel.  Finding a line between trusted and untrusted information on tweets through sequence classification.  In 2021 International Conference on Military Communication and Information Systems (ICMCIS), pages 1–6. IEEE, 2021.
  * [7] Ganesh Gopal Devarajan, Senthil Murugan Nagarajan, Sardar Irfanullah Amanullah, SA Sahaaya Arul Mary, and Ali Kashif Bashir.  Ai-assisted deep nlp-based approach for prediction of fake news from social media users.  IEEE Transactions on Computational Social Systems, 2023.
  * [8] Muhammad Asfand-e Yar, Qadeer Hashir, Syed Hassan Tanvir, and Wajeeha Khalil.  Classifying misinformation of user credibility in social media using supervised learning.  Computers, Materials & Continua, 75(2), 2023.
  * [9] Faraz Ahmad and Syed Afzal Murtaza Rizvi.  Information credibility on twitter using machine learning techniques.  In Futuristic Trends in Networks and Computing Technologies: Second International Conference, FTNCT 2019, Chandigarh, India, November 22–23, 2019, Revised Selected Papers 2, pages 371–381. Springer, 2020.
  * [10] Tanveer Khan and Antonis Michalas.  Trust and believe-should we? evaluating the trustworthiness of twitter users.  In 2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), pages 1791–1800. IEEE, 2020.
  * [11] Tanveer Khan and Antonis Michalas.  Seeing and believing: Evaluating the trustworthiness of twitter users.  IEEE Access, 9:110505–110516, 2021.
  * [12] Jingwen Wang, Xuyang Jing, Zheng Yan, Yulong Fu, Witold Pedrycz, and Laurence T Yang.  A survey on trust evaluation based on machine learning.  ACM Computing Surveys (CSUR), 53(5):1–36, 2020.
  * [13] Shamshe Alam, Sanjay Kumar Sonbhadra, Sonali Agarwal, and P Nagabhushan.  One-class support vector classifiers: A survey.  Knowledge-Based Systems, 196:105754, 2020.
  * [14] Aysen Degerli, Fahad Sohrab, Serkan Kiranyaz, and Moncef Gabbouj.  Early myocardial infarction detection with one-class classification over multi-view echocardiography.  In 2022 Computing in Cardiology, volume 498, pages 1–4. IEEE, 2022\.
  * [15] Fahad Sohrab and Jenni Raitoharju.  Boosting rare benthic macroinvertebrates taxa identification with one-class classification.  In 2020 IEEE Symposium Series on Computational Intelligence, pages 928–933. IEEE, 2020.
  * [16] Zaffar Zaffar, Fahad Sohrab, Juho Kanniainen, and Moncef Gabbouj.  Credit card fraud detection with subspace learning-based one-class classification.  In 2023 IEEE Symposium Series on Computational Intelligence (SSCI), pages 407–412. IEEE, 2023.
  * [17] Bernhard SchölkopfÜ, Robert C Williamson, Alex SmolaÜ, and John Shawe-TaylorÝ.  Sv estimation of a distribution’s support.  Adv. Neural Inf. Process. Syst, 41:582–588, 2000.
  * [18] Vasileios Mygdalis, Alexandros Iosifidis, Anastasios Tefas, and Ioannis Pitas.  Graph embedded one-class classifiers for media data classification.  Pattern Recognition, 60:585–595, 2016.
  * [19] Fahad Sohrab, Alexandros Iosifidis, Moncef Gabbouj, and Jenni Raitoharju.  Graph-embedded subspace support vector data description.  Pattern Recognition, 133:108999, 2023.
  * [20] Fahad Sohrab, Jenni Raitoharju, Moncef Gabbouj, and Alexandros Iosifidis.  Subspace support vector data description.  In 2018 24th International Conference on Pattern Recognition (ICPR), pages 722–727. IEEE, 2018.
  * [21] Stefanie Haustein, Timothy D Bowman, Kim Holmberg, Andrew Tsou, Cassidy R Sugimoto, and Vincent Larivière.  Tweets as impact indicators: Examining the implications of automated “bot” accounts on t witter.  Journal of the Association for Information Science and Technology, 67(1):232–238, 2016.
  * [22] Qiang Fu, Bo Feng, Dong Guo, and Qiang Li.  Combating the evolving spammers in online social networks.  Computers & Security, 72:60–73, 2018.
  * [23] Jorge Rodríguez-Ruiz, Javier Israel Mata-Sánchez, Raul Monroy, Octavio Loyola-Gonzalez, and Armando López-Cuevas.  A one-class classification approach for bot detection on twitter.  Computers & Security, 91:101715, 2020.
  * [24] Marion Meyers, Gerhard Weiss, and Gerasimos Spanakis.  Fake news detection on twitter using propagation structures.  In Disinformation in Open Online Media: Second Multidisciplinary International Symposium, MISDOOM 2020, Leiden, The Netherlands, October 26–27, 2020, Proceedings 2, pages 138–158. Springer, 2020.
  * [25] Pedro Henrique Arruda Faustini and Thiago Ferreira Covoes.  Fake news detection in multiple platforms and languages.  Expert Systems with Applications, 158:113503, 2020.
  * [26] Naeemul Hassan, Fatma Arslan, Chengkai Li, and Mark Tremayne.  Toward automated fact-checking: Detecting check-worthy factual claims by claimbuster.  In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1803–1812, 2017.
  * [27] Nojun Kwak.  Nonlinear projection trick in kernel methods: An alternative to the kernel trick.  IEEE Transactions on Neural Networks and Learning Systems, 24(12):2113–2119, 2013.
  * [28] Fahad Sohrab, Jenni Raitoharju, Alexandros Iosifidis, and Moncef Gabbouj.  Ellipsoidal subspace support vector data description.  IEEE Access, 8:122013–122025, 2020.
  * [29] Fahad Sohrab, Firas Laakom, and Moncef Gabbouj.  Newton method-based subspace support vector data description.  In 2023 IEEE Symposium Series on Computational Intelligence (SSCI), pages 1372–1379. IEEE, 2023.
  * [30] Fahad Sohrab, Jenni Raitoharju, Alexandros Iosifidis, and Moncef Gabbouj.  Multimodal subspace support vector data description.  Pattern Recognition, 110:107648, 2021.


# Investigating the Indirect Object Identification circuit in Mamba

Danielle Ensign  Adrià Garriga-Alonso

###### Abstract

How well will current interpretability techniques generalize to future models?
A relevant case study is Mamba, a recent recurrent architecture with scaling
comparable to Transformers. We adapt pre-Mamba techniques to Mamba and
partially reverse-engineer the circuit responsible for the Indirect Object
Identification (IOI) task. Our techniques provide evidence that 1) Layer 39 is
a key bottleneck, 2) Convolutions in layer 39 shift names one position
forward, and 3) The name entities are stored linearly in Layer 39’s SSM.
Finally, we adapt an automatic circuit discovery tool, positional Edge
Attribution Patching, to identify a Mamba IOI circuit. Our contributions
provide initial evidence that circuit-based mechanistic interpretability tools
work well for the Mamba architecture.

Machine Learning, Mechanistic Interpretability, Mamba, State Space Models,
Large Language Models, ICML

##  1 Introduction

If we care about using interpretability on new models, we should know: Will
interpretability techniques generalize to new architectures?

To investigate this question, we apply existing mechanistic interpretability
techniques to a new model developed after most interpretability techniques:
Mamba. Mamba is a State Space Model (SSM), a type of recurrent neural network
(Gu & Dao, 2023). Mamba is the result of years of work on language modeling
with state space models (Gu et al., 2020, 2022; Fu et al., 2023), and is one
of many new RNN-like architectures (Beck et al., 2024; Peng et al., 2023; Gu &
Dao, 2023; Lieber et al., 2024). These RNNs have scaling competitive with
Transformers, unlike LSTMs (Kaplan et al., 2020). Because it is a recurrent
network, it only needs to store hidden states from the previous token,
resulting in faster inference. The recurrence is also linear (and thus
associative) over token position, which permits further optimizations. See
Appendix for architecture details.

While we are the first to focus on finding circuits in Mamba, previous work
has shown other interpretability techniques apply. For example, Sharma et al.
(2024) locate and edit factual information with ROME (Rank One Model Editing)
Meng et al. (2023). Ali et al. (2024) extract hidden attention matrices, and
Torres (2024); Grazzi et al. (2024) use linear probes to identify
capabilities. Additionally, Paulo et al. (2024) showed that Contrastive
Activation Addition (Rimsky et al., 2024), Tuned Lens (Belrose et al., 2023)
and probes to elicit latent knowledge (Mallen et al., 2024) transfer to the
Mamba architecture.

This work focuses on applying techniques from circuit-based mechanistic
interpretability to Mamba to see how well these techniques transfer to new
architectures. In particular, we study state-spaces/mamba-370m, a 370-million-
parameter Mamba model pretrained (Gu & Dao, 2023) on The Pile (Gao et al.,
2020). We chose this model as it is the smallest Mamba model with good
performance ($\sim 96\%$ accuracy on our templates) on the Indirect Object
Identification (IOI) task (Wang et al., 2023).

In particular, for the IOI task, we:

  1. 1.

Show multiple lines of evidence suggesting layer 39 is a bottleneck:

    1. (a)

Zero and Resample ablation (Section 3.1.4) experiments point to layer 39 and
layer 0.

    2. (b)

We compute greedy minimal subsets of layers allowed to transfer information
across tokens (“token cross-talk”). These always include layer 39 (but layer 0
only 18% of the time).

  2. 2.

Provide evidence that the convolution on layer 39 shifts name data to the next
token position.

  3. 3.

Modify the representations used by layer 39 using averages of activations,
resulting in overwriting one output name with another (Rimsky et al., 2024).
These results suggest that in the SSM of layer 39, entity names are linearly
represented, with different representations for the first and second time (or
sentence) the names appear in IOI.

  4. 4.

Provide multiple lines of evidence that layer 39 writes outputs into only the
final token position:

    1. (a)

Resample ablation on the hidden state and the values added to the residual
stream.

    2. (b)

A slight modification of the results of EAP gives us a subgraph that is
capable of doing IOI while only leaving layer 39’s final token’s outputs
unpatched.

Figure 1: Our hypothesis for the role of Layer 39. The representations of
n1–n3 and n4–n5 are interchangeable over positions.

In addition, we show that ACDC and Edge Attribution Patching (Syed et al.,
2023) both result in sparse graphs when applied to IOI on Mamba, and provide
the resulting computational graphs.

##  2 The Test Subject: Mamba

Here we provide a brief overview of the Mamba architecture. We refer the
reader to Ensign et al. (2024) for a more detailed introduction. We use
$\stackrel{{\scriptstyle[A,B]}}{{v}}$ to denote that variable $v$ has shape
$[A,B]$.

###  2.1 State Space Model (SSM)

Mamba’s SSM block can be written as mapping a 1D space to a N-dimensional
state space, then back to a 1D space:

$\displaystyle\stackrel{{\scriptstyle[N]}}{{h_{t}}}$
$\displaystyle=\stackrel{{\scriptstyle[N,N]}}{{\overline{A}}}\stackrel{{\scriptstyle[N]}}{{h_{t-1}}}+\stackrel{{\scriptstyle[N,1]}}{{\overline{B}}}\stackrel{{\scriptstyle[1]}}{{x_{t}}}$
(1) $\displaystyle\stackrel{{\scriptstyle[1]}}{{y_{t}}}$
$\displaystyle=\stackrel{{\scriptstyle[1,N]}}{{C}}\stackrel{{\scriptstyle[N]}}{{h_{t}}}+\stackrel{{\scriptstyle[1,1]}}{{D}}\stackrel{{\scriptstyle[1]}}{{x}}_{t}$
(2)

In Mamba $A$ is diagonal, so we will just write it as
$\stackrel{{\scriptstyle[N]}}{{\overline{A}}}$ and do an element-wise product
“$\odot$”.

Each layer does $E$ of these in parallel. $A$ has a separate value for each
$e$, and is encoded as an $[E,N]$ matrix. We can denote $\overline{A_{e}}$ as
the $N$-sized entry for stream $e$, giving us,

$\displaystyle\stackrel{{\scriptstyle[N]}}{{h_{t,e}}}$
$\displaystyle=\stackrel{{\scriptstyle[N]}}{{\overline{A_{e}}}}\odot\stackrel{{\scriptstyle[N]}}{{h_{t-1,e}}}+\stackrel{{\scriptstyle[N,1]}}{{\overline{B}}}\stackrel{{\scriptstyle[1]}}{{x_{t,e}}}$
(3) $\displaystyle\stackrel{{\scriptstyle[1]}}{{y_{t,e}}}$
$\displaystyle=\stackrel{{\scriptstyle[1,N]}}{{C}}\stackrel{{\scriptstyle[N]}}{{h_{t,e}}}+\stackrel{{\scriptstyle[1,1]}}{{D}}\stackrel{{\scriptstyle[1]}}{{x}}_{t,e}$
(4)

Finally, $\overline{A}_{e}$, $\overline{B}$, and $C$ depend on the SSM input,
and so gain a subscript $t$. $\overline{B}$ also gains a subscript $e$ through
the variable time-step, $\stackrel{{\scriptstyle[1]}}{{\Delta_{t,e}}}$. The
final SSM expressions are:

$\displaystyle\stackrel{{\scriptstyle[N]}}{{h_{t,e}}}$
$\displaystyle=\stackrel{{\scriptstyle[N]}}{{\overline{A_{t,e}}}}\odot\stackrel{{\scriptstyle[N]}}{{h_{t-1,e}}}+\stackrel{{\scriptstyle[N,1]}}{{\overline{B_{t,e}}}}\stackrel{{\scriptstyle[1]}}{{x_{t,e}}}$
(5) $\displaystyle\stackrel{{\scriptstyle[1]}}{{y_{t,e}}}$
$\displaystyle=\stackrel{{\scriptstyle[1,N]}}{{C_{t}}}\stackrel{{\scriptstyle[N]}}{{h_{t,e}}}+\stackrel{{\scriptstyle[1,1]}}{{D}}\stackrel{{\scriptstyle[1]}}{{x}}_{t,e},$
(6)

where

$\displaystyle\stackrel{{\scriptstyle[N]}}{{\overline{A_{t,e}}}}$
$\displaystyle=\exp(-\stackrel{{\scriptstyle[1]}}{{\Delta_{t,e}}}\exp(A_{\text{log}})_{e}),$
(7) $\displaystyle\stackrel{{\scriptstyle[N]}}{{\overline{B_{t,e}}}}$
$\displaystyle=\stackrel{{\scriptstyle[1]}}{{\Delta_{t,e}}}\stackrel{{\scriptstyle[N]}}{{B_{t}}},\quad\quad\text{with}\stackrel{{\scriptstyle[N]}}{{,}}{B_{t}}=\stackrel{{\scriptstyle[N,E]}}{{W_{B}}}\stackrel{{\scriptstyle[E]}}{{x_{t}}},$
(8) $\displaystyle\stackrel{{\scriptstyle[N]}}{{C_{t}}}$
$\displaystyle=\stackrel{{\scriptstyle[N,E]}}{{W_{C}}}\stackrel{{\scriptstyle[E]}}{{x_{t}}},$
(9) $\displaystyle\stackrel{{\scriptstyle[1]}}{{\Delta_{t,e}}}$
$\displaystyle=\text{softplus}(\stackrel{{\scriptstyle[E]}}{{x_{t}}}\cdot\stackrel{{\scriptstyle[E]}}{{W^{\Delta}_{e}}}+\stackrel{{\scriptstyle[1]}}{{B^{\Delta}_{e}}}),$
(10)

with
$\stackrel{{\scriptstyle[E,E]}}{{W^{\Delta}}},\stackrel{{\scriptstyle[E]}}{{B^{\Delta}}},\stackrel{{\scriptstyle[N,E]}}{{W_{B}}},\stackrel{{\scriptstyle[N,E]}}{{W_{C}}},\stackrel{{\scriptstyle[N,E]}}{{A_{\text{log}}}}$
being learned parameters, and $\text{softplus}(x)=\log(1+e^{x})$. This
parameterization guarantees that $\overline{A}<1$, and thus the hidden state
does not explode.

###  2.2 Architecture

Mamba has multiple layers which each add to a residual stream. Each layer
does:

  * •

Project input $\overset{[B,L,D]}{\text{resid}}$ to $\overset{[B,L,E]}{x}$

  * •

Project input $\overset{[B,L,D]}{\text{resid}}$ to
$\overset{[B,L,E]}{\text{skip}}$

  * •

Conv over the time dimension, with a different filter for each $e\in[E]$
($x=\text{conv}(x)$)

  * •

Apply non-linearity (silu) ($x=\text{silu}(x)$)

  * •

$y=SSM(x)$

  * •

Gating: $y=y*\text{silu}(\text{skip})$

  * •

Project $\overset{[B,L,E]}{y}$ to $\overset{[B,L,D]}{\text{output}}$

Where $B$ is batch size, $L$ is context length, $D$ is embedding dimension,
and $\text{silu}(x)=x*\text{sigmoid}(x).$ See Figure 2.

##  3 Circuit-based Mechanistic Interpretability

To understand how large language models (LLMs) implement their emergent
capabilities (Wei et al., 2022), we focus on finding human-interpretable
algorithms (Olah, 2022). This involves representing models as computational
graphs and identifying circuits that are subsets of that computational graph.
Ideally, each subgraph would also be annotated to describe the role of each
component (Geiger et al., 2021).

Finding circuits that capture the behavior on all inputs is intractable for
large language models. Therefore, we study behavior on specific tasks.

###  3.1 Problem Description

Following (Geiger et al., 2021; Conmy et al., 2023): we have a behavior (task)
that we would like to study, a metric for evaluating performance, and a
coarse-grained computational graph of the neural network on which we express
explanations. We would like to find the minimal subgraph that attains a high
enough metric score (where target metric score is a hyperparameter), with an
explanation of what variations in the data each graph component captures.

####  3.1.1 IOI Task

We are studying the IOI task, initially examined by (Wang et al., 2023).
Consider an example data point:

    Friends Isaac, Lucas and Lauren went to
    the office. Lauren and Isaac gave a
    necklace to

The model is asked to predict the next token, and the correct answer is “
Lucas”. “ Lucas” is the Indirect Object we are trying to identify. See the
Appendix for detailed data-generation templates and corruption information.

####  3.1.2 Metric

There are many choices of metrics: KL-Divergence, Logit Diff, Accuracy,
Probability of the correct answer, etc. The best metric to use in general is
an open question and may be task specific. For IOI, Zhang & Nanda (2024)
suggest the Normalized Logit Diff metric, as that helps propagate information
missed by accuracy. See the Appendix for further details.

####  3.1.3 Computational Graph

We use the MambaLens library (see also Nanda & Bloom (2022)) to intervene at
different locations per experiment.

Figure 2: A single layer in the Mamba architecture, with hook points listed in
all the locations we intervene. Note that the SSM contains further hook
points, described in Section 4.3, “Controlling model output”. The “SSM” and
“conv” components are affected by previous time steps.

  * •

Section 4.1.1 “Resample Ablation” uses blocks.{layer}.hook_layer_input.

  * •

Section 4.1.2 “Layer Removal” uses blocks.{layer}.hook_out_proj.

  * •

Section 4.1.3 “Removing Cross Talk” uses blocks.{layer}.hook_in_proj.

  * •

Section 4.2 “Layer 39 Uses Conv to Shift Names One Position Forward” uses
blocks.{layer}.hook_in_proj and blocks.{layer}.hook_conv.

  * •

Section 4.3 “Controlling model output by modifying representations on layer
39” uses blocks.{layer}.hook_ssm_input. For the cosine sim plots, it uses
further hooks inside the ssm, described in Appendix.

  * •

Section 4.4 “Layer 39 moves information into only the last token position”
uses blocks.{layer}.hook_h.{token_pos}, blocks.{layer}.hook_out_proj, and the
hooks used in Section D

  * •

Both Section D “EAP” runs use blocks.{layer}.hook_layer_input and
blocks.{layer}.hook_layer_output. They also use hook_embed (described the next
section) as the input node, and blocks.47.hook_resid_post as the output node.

  * •

The “ACDC” (Section D.2) run following the (non positional) EAP run uses all
the hooks from the EAP runs. It also uses blocks.{layer}.hook_skip,
blocks.{layer}.hook_conv, and blocks.{layer}.hook_ssm_input.

Note that blocks.{layer}.hook_layer_input is the residual stream before
normalization. If we patched directly on these, it would modify downstream
values as well. Thus, to patch only a single layer’s input, we clone this
value first.

####  3.1.4 Ablations

To identify which nodes and edges are important, we take inspiration from
causal inference (Pearl, 2009): ablate nodes of our computational graph and
observe changes in the output.

Replacing activations with zero (Olsson et al., 2022; Cammarata et al., 2021)
or the mean over many data points (Wang et al., 2023) was initially used.
However, these can result in activations that are out of distribution (Chan et
al., 2022). _Resample ablation_ (Geiger et al., 2021), also known as
_interchange interventions_ and _causal tracing_ , is a commonly used
alternative (Hanna et al., 2023; Heimersheim & Janiak, 2023; Wang et al.,
2023; Conmy et al., 2023). Resample ablation begins by running a forward pass
with a _corrupted_ prompt, then substitutes those corrupted activations into a
forward pass run on the uncorrupted prompt.

In addition to resample ablation, in Mamba (and Transformers), the residual
stream is a sum of outputs from every layer. This allows us to create an edge
between every layer (Elhage et al., 2021), see Figure 3.

Figure 3: Fully connected causal graph, using the additivity of the residual
stream. This is an example network with 4 layers, so the output node is
blocks.3.hook_resid_post. The full network we study has 48 layers, so the
output node is blocks.47.hook_resid_post

To patch an edge this causal graph (Elhage et al., 2021) going from layer $i$
to layer $j$, we can do:

$\displaystyle\begin{aligned} \overset{[B,L,D]}{\text{patched
input}_{j}}=&\overset{[B,L,D]}{\text{input}_{j}}-\overset{[B,L,D]}{\text{output}_{i}}+\overset{[B,L,D]}{\text{corrupted
output}_{i}}\end{aligned}$ (11)

We give the dimensions of our tensors in square brackets [ ] above the term.
Here, $B$ is batch size, $L$ is context length, and $D$ is embedding
dimension. The $\text{output}_{i}$ is blocks.i.hook_out_proj, computed during
the same forward pass as the $\text{input}_{j}$ and $\text{patched input}_{j}$
(which both use blocks.j.hook_layer_input). $\text{corrupted output}_{i}$ are
stored values from a separate forward pass using the corrupted prompt and
blocks.i.hook_out_proj.

###  3.2 Semi-automatic Circuit Discovery

Initially, finding circuits had to be done by hand: patching subsets of nodes
and edges (known as path patching (Goldowsky-Dill et al., 2023)) until a
circuit emerges. Several methods have since been developed to automate this
process. Subnetwork probing learns a mask over the graph using gradient
descent (Cao et al., 2021). Automated Circuit DisCovery (ACDC) starts from
sink nodes and works backwards to reconstruct the causal graph (Conmy et al.,
2023). ACDC requires a separate forward pass for every edge, and this can be
very time-consuming. Head Importance Score for Pruning (Michel et al., 2019),
and more recently EAP (Edge Attribution Patching) (Syed et al., 2023), use the
gradient to approximate the contribution of all edges simultaneously. In
particular, EAP approximates the _attribution scores_ of an edge between layer
$i$ and layer $j$ via:

$\displaystyle\begin{aligned} \overset{[B,L,D]}{\text{attr}_{i\mapsto
j}}=(\overset{[B,L,D]}{-\text{output}_{i}}+\overset{[B,L,D]}{\text{corrupted
output}_{i}})\nabla\overset{[B,L,D]}{\text{input}_{j}}\end{aligned}$ (12)

Where $\nabla\text{input}_{j}$ is the gradient given from the backward hook
made in these steps:

  1. 1.

For every layer, create a backward hook on blocks.j.hook_layer_input

  2. 2.

Run a forward pass that patches every edge

  3. 3.

Compute the metric on the resulting logits, and call backward on the metric’s
value.

To get an attribution for each edge, we sum $\text{attr}_{i\mapsto j}$ over
the $L$ and $D$ axes, then mean over the $B$ axis.

This approximation can be improved by using integrated gradients (Marks et
al., 2024; Sundararajan et al., 2017): compute a separate
$\overset{[B,L,D]}{\text{attr}_{i\mapsto j}}(\overset{[1]}{\alpha_{k}})$ for
an $\overset{[1]}{\alpha_{k}}=k/(\text{ITERS}-1)$ where
$k\in[0,\ldots,\text{ITERS}-1]$, then compute the average of all these scores
(ITERS is an int hyperparameter that determines how fine grained our
approximation is, usually 5-10 is large enough). The attribution is computed
in using Equation 12 like before, however, the forward pass for a given
$\alpha_{k}$ only “partially” applies every patch as follows:

$\displaystyle\begin{aligned} \overset{[B,L,D]}{\text{patched
input}_{j}}=\overset{[B,L,D]}{\text{input}_{j}}-\overset{[1]}{\alpha_{k}}(\overset{[B,L,D]}{\text{output}_{i}}+\overset{[B,L,D]}{\text{corrupted
output}_{i}})\end{aligned}$ (13)

Once we have these attribution scores, we can sort all edges by their
attribution and perform a binary search to find the minimal set of edges that
achieves our desired metric.

The major downside of these automated methods is that (aside from token-level
attributions) they do not yet assign interpretations to nodes.

##  4 Findings

###  4.1 Layer 39 is Important

We have three lines of evidence suggesting layer 39 is important. While two of
these lines of evidence also suggest layer 0 is important, we also provide
evidence that token cross-talk in layer 0 is not usually needed.

####  4.1.1 Resample Ablation

To determine which layers are important, we will resample ablate
blocks.{layer}.hook_layer_input. To determine which tokens matter, we do this
patch separately for each (layer, token_position) pair. This forces us to
limit to the three templates that share name token positions (one could use
more templates and use semantic labels instead of token positions, but that is
left to future work).

Because each corruption affects different positions, averaging over them does
not make sense. Thus, we show results separately for each corruption. We focus
on 3-name templates. While 2-name templates are simpler, we find results from
2-name templates to be misleading as the task is too simple.

Figure 4:  Displayed is 1 - (Normalized logit diff) for each (layer, position)
patch, averaged over 80 data points. 0 corresponds to acting like the
uncorrupted forward pass, and 1 corresponds to acting like the corrupted
forward pass. The y-axis is Layer, and the x-axis is token position. The
corruptions can be observed by inspecting the token position labels. Each of
the five plots correspond to different IOI patches.

Figure 4 shows that normalized logit diff changes most when patching layer 0
and 39.

####  4.1.2 Layer Removal

Each layer adds to the residual stream. This allows us to “remove” a layer by
setting this added value to zero, i.e., zero-ablating layer outputs
(blocks.{layer}.hook_proj_out). We plot probability of the correct answer, as
there is no corrupted answer to compare to.

Figure 5: Relative probability of the correct token when zero-ablating each
layer’s outputs. Relative probability is the softmax over the 4 logits from
prompt and corruption names. The clean model gets 83%.

In Figure 5, we again see that, layers 0 and 39 are crucial parts of the
circuit that cannot be removed.

We also find that by repeatedly removing the layer that decreases accuracy the
least, about half of the layers can be removed with minimal impact on
accuracy. We replicated this layer removal robustness on GPT-2-Small (Radford
et al., 2019). This might be seen as evidence for the residual stream having a
privileged basis that is consistent between layers. However, it is also
consistent with there being multiple distinct spaces (for example, embed-0,
0-39, 39-out), or layers being simultaneously compatible with multiple
different spaces. See Belrose et al. (2023) for more discussion on this
“privileged basis” perspective.

####  4.1.3 Removing Token Cross-Talk

It would be useful to know where information travels between tokens, as
opposed to just modifying the representations in place. We conduct an
experiment to find a small set of layers that do this “token cross-talk”.

There are two ways in which a layer at a specific token position can affect
future positions (“token cross-talk”): the convolutional (conv) layer, and the
SSM block. (For clarity, in transformers, attention is where “token cross-
talk” occurs, as that is where information can flow between different token
positions)

Putting corrupted data into the conv will also put corrupted data into the
SSM, as it is downstream of the conv. Thus, to remove a specific layer’s
ability to have token cross-talk, we can apply resample ablation to that
layer’s conv inputs (blocks.{layer}.hook_in_proj) at all positions. Because we
also patched convs in previous positions, the SSM will only have information
about the corrupted input.

If we patch every layer before $L$ in the manner above, this removes any
information about previous tokens at layer $L$. However, if we only patch some
previous layers, the previous tokens can have influence: a previous layer
could move two tokens into the same position, and then a later layer could
process those token interactions in place.

Also, note that this does not completely remove “cross talk”, it only removes
cross talk that is specific to the uncorrupted prompt (i.e., cross talk that
is needed for outputting the correct answer). Cross talk that occurs in both
uncorrupted and corrupted prompts will still occur. This is somewhat
acceptable because we only care about task-relevant cross talk.

Given these two disclaimers, we still feel this is a useful proxy for
“removing cross talk”.

Now, start with patching all layers’ cross talk, then “unpatch” the layer that
improves accuracy the most. This is repeated until accuracy is about 0.9,
resulting in a “minimal cross talk circuit” that can perform the task. We do
this separately for each (corruption, template) pair.

Figure 6: Out of all (corruption, template) pairs, the proportion of times a
given layer was in the minimal cross talk circuit.

In Figure 6, we see that Layers 39 and 15 appear in every minimal circuit
found. Layer 15 seems worthy of investigation in future work, as these two
also stand out in EAP. Inspecting the logs, Layer 39 is always the first layer
added and has a large effect.

In 82% of these minimal circuits, Layer 0 did not appear. This is strong
evidence that for the majority of (corruption, template) pairs, computation
Layer 0 does is in-place and not cross talk.

In Transformers, it is suspected that layer 0 is responsible for multi-token
embeddings (Nanda et al., 2023). These results suggest something else happens
in Mamba. However, because all of our prompts use single token names, it is
possible that these capabilities are simply not needed for this task (but
still exist).

###  4.2 Layer 39 Uses Conv to Shift Names One Position Forward

When examining the hidden state, we can display the cosine similarity of a
token’s contribution to the current state with future (and previous) hidden
states. This allows us to see how much the value was “kept around” (see
Appendix for more information on the hooks used here).

Figure 7: Cosine Similarity between the current token’s contribution to $h$
(which is $\overset{[B,E,N]}{\bar{B_{i}}}\overset{[B,E,1]}{x_{i}}$, each $i$
is on the x axis), and the hidden state ($\overset{[B,E,N]}{h_{j}}$ each $j$
is on the y axis)

As this is not causal, it should not be relied on too heavily. The structure
seems to be name-dependent; we show three representative examples in Figure 7.

What stands out is that the horizontal lines are one token after each name.
This could either mean that 1) A previous layer shifted the tokens over, or 2)
Layer 39 shifted the tokens over using the conv.

To distinguish between these, we can do resample ablation on the individual
conv “slices”: The conv can be seen as four $E$-sized “slice” vectors for each
(-3,-2,-1,0) relative token position, that are multiplied (element-wise) by
the corresponding $E$-sized token representations.

  * •

If hypothesis 1 were true, we should see the 0 conv slice at token position +
1 have a large value.

  * •

If hypothesis 2 were true, we should see the -1 conv slice at token position +
1 have a large value.

Figure 8: This is 1 - Normalized Logit Diff when patching on the given conv
slice. 0 corresponds to acting like uncorrupted, 1 corresponds to acting like
corrupted. The x-axis is conv slices (-2, -1, then 0) for layer 39. The y-axis
is token position; observe the labels to see which corruption was used.

Figure 8 supports hypothesis 2, that Layer 39 uses conv to shift names one
position forward.

We did some tests to investigate multi-token names and found the cosine
similarity plots always have lines at the position after the first token of
the name (possibly other layers handle multi-token names). It is also worth
nothing that we see the horizontal lines for entities, not just names.

We do not yet know why this shifting behavior occurs, and leave that question
for future work.

###  4.3 Controlling Model Output by Modifying Representations on Layer 39

We hypothesize that the representations in the SSM are linear because, on a
single layer, the mechanism it has to add or remove information from tokens is
linear in h.

We tried to visualize $\stackrel{{\scriptstyle[1]}}{{\Delta_{t,e}}}$ adding or
removing information to various parts but did not find it very insightful.
Instead, to investigate whether the internal representation of Layer 39 SSM is
linear, we do the following:

  1. 1.

Create a large IOI dataset. For each data point, store the activations of each
name’s blocks.39.hook_ssm_input. We use the activation at the token position
one after the name, because of the shifting behavior we observed earlier.

  2. 2.

For each name, average the representations. Store a separate average for, say,
“John” in the first position, “John” in the second position, etc. We use
enough data points that each (name, position) pair gets 50-100 values to
average over.

  3. 3.

_Replace Method_ : To write a different name, simply substitute the SSM input
at that position with the averaged value from a different name.

  4. 4.

_Subtract and Add Method_ Instead of substituting, subtract the current name’s
average and add the substituted name’s average.

We find that the Replace Method works adequately, while the Subtract and Add
Method works surprisingly well, changing the logits to the desired output more
than 95% of the time.

One thing to note: It was possible that the SSM was using the representations
from the name’s token position, as well as the name’s token position + 1.
Patching on conv slices was initial evidence this did not occur, and the
efficacy of this replacement procedure provides further evidence that this is
not the case.

Having a separate average for each position also lets us test if token
position is an important part of the representation. If it is, we should
expect that “John” at name position 2 should not be easily substituted for
“Mary” at name position 0.

Figure 9: Proportion of data where logit of the corrupted name is higher than
the logit of original name, using the two methods described in Section 4.3.
The x-axis is the position the average was computed from, the y-axis is the
position being substituted. To substitute into the fourth and fifth positions,
we substitute the correct answer (instead of a patched name).

Instead, in Figure 9 we find that the first three name positions are
compatible, while the fourth and fifth positions are much less compatible.

####  4.3.1 Compatibility of first three name positions

The compatibility of the first three name’s representations could either
suggest:

  * •

The IOI circuit does not store positional information in the first three
names, or

  * •

There are circuits to handle incorrectly encoded positional information, which
got activated and handled our patching well despite having incorrect
positional data

Distinguishing between these is left for future work.

####  4.3.2 Incompatibility of fourth and fifth name positions

Consider one of our data points: “Friends Isaac, Lucas and Lauren went to the
office. Isaac and Lucas gave a necklace to” (answer is “ Lauren”)

We see that when names occur in the fourth or fifth position, it is the second
time they occur in the prompt.

One hypothesis is that the conv sees a period and encodes that in the name
representation. However, while the model we study (mamba-370m) has four conv
slices, we find that the conv slice attending to the -3 position is always
zero, likely due to a bug in the Mamba training code. Thus, it can only attend
to the previous 2 positions in practice (the third conv slice is for attending
to the current position). This means that the name in the fifth position’s
representation is not distinguishable from the name in the third position by
the conv.

Thus, some token cross-talk must be happening in a layer before 39. As
mentioned above, for 82% of (corruption, template) pairs, cross-talk in layer
0 is not needed. So while these experiments provide strong evidence that layer
39 is a bottleneck, more circuit analysis is needed.

###  4.4 Layer 39 moves information into only the last token position

We can do resample ablation on the ssm hidden state via
blocks.{layer}.hook_h.{token_pos}.

Figure 10 shows that it only uses the hidden states one after the ablated
token, in line with 4.2. We also see that hidden state values are used all the
way to the last token position.

This tells us that the answer-relevant information is moved into the last
token position. However, it is possible that information is also sent to
other, earlier positions as well.

To test for this, we can do resample ablation on blocks.{layer}.hook_proj_out,
which is the value added to the residual stream at the end of each layer.

In Figure 11 we see that only the last index is used.

In addition, positional EAP (Section D.3.5) suggests that other (non-last
token) connections are important, as they are preserved in the set of edges
that get 85%. However their attribution scores are very low. Manually removing
all the non-last token connections going out from layer 39 only reduces
accuracy from 85.2% to 83.8%, and reduces normalized logit diff from to 0.877
to 0.873. This suggests that either there is backup behaviour activated when
those positions are patched, or that these connections are mostly spurious and
not essential parts of the circuit.

These three lines of evidence together strongly suggest that the task-relevant
information provided by layer 39 is stored only in the last token position.

##  5 Positional Edge Attribution Patching (Positional EAP)

Here we describe a simple modification to EAP that allows us to have token-
level edge attributions.

Typically, in EAP, after we compute $\overset{[B,L,D]}{\text{attr}_{i\mapsto
j}}$ we sum over the $L$ and $D$ dimensions, then take the mean over the $B$
dimension to get an attribution for each edge.

Instead, we will just sum over the $D$ dimension and mean over the $B$
dimension, giving us an attribution for every (edge, position). See Appendix
D.

The results of EAP further emphasize the importance of Layer 39. However,
there is also significant activity elsewhere that merit further analysis.

##  6 Future Work

There are still many open questions we have about the IOI circuit in
mamba-370m. Future work can focus on:

  * •

Analysis of what cross talk is done before layer 39

  * •

Analysis of what the later layers are doing to decode the answer encoded in
the final token position

  * •

Training Sparse Autoencoders (SAEs) and using EAP to make a feature circuit
capable of doing the task, to get a more fine grained analysis (similar to
work in Marks et al. (2024))

  * •

Conducting similar analysis on other tasks (such as docstring (Heimersheim &
Janiak, 2023) or greater than (Hanna et al., 2023))

##  7 Reproducibility

All code for experiments can be found at
https://github.com/Phylliida/investigating-mamba-ioi. All experiments were
conducted on a RTX A6000.

## References

  * Ali et al. (2024) Ali, A., Zimerman, I., and Wolf, L.  The hidden attention of mamba models, 2024.
  * Beck et al. (2024) Beck, M., Pöppel, K., Spanring, M., Auer, A., Prudnikova, O., Kopp, M., Klambauer, G., Brandstetter, J., and Hochreiter, S.  xlstm: Extended long short-term memory, 2024.  URL https://arxiv.org/abs/2405.04517.
  * Belrose et al. (2023) Belrose, N., Furman, Z., Smith, L., Halawi, D., Ostrovsky, I., McKinney, L., Biderman, S., and Steinhardt, J.  Eliciting latent predictions from transformers with the tuned lens, 2023.
  * Cammarata et al. (2021) Cammarata, N., Goh, G., Carter, S., Voss, C., Schubert, L., and Olah, C.  Curve circuits.  _Distill_ , 2021.  doi: 10.23915/distill.00024.006.  https://distill.pub/2020/circuits/curve-circuits.
  * Cao et al. (2021) Cao, S., Sanh, V., and Rush, A.  Low-complexity probing via finding subnetworks.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pp. 960–966, Online, 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.naacl-main.74.  URL https://aclanthology.org/2021.naacl-main.74.
  * Chan et al. (2022) Chan, L., Garriga-Alonso, A., Goldowsky-Dill, N., Greenblatt, R., Nitishinskaya, J., Radhakrishnan, A., Shlegeris, B., and Thomas, N.  Causal scrubbing: A method for rigorously testing interpretability hypotheses.  Alignment Forum, 2022.  URL https://www.alignmentforum.org/posts/JvZhhzycHu2Yd57RN/causal-scrubbing-a-method-for-rigorously-testing.
  * Conmy et al. (2023) Conmy, A., Mavor-Parker, A. N., Lynch, A., Heimersheim, S., and Garriga-Alonso, A.  Towards automated circuit discovery for mechanistic interpretability, 2023.
  * Elhage et al. (2021) Elhage, N., Nanda, N., Olsson, C., Henighan, T., Joseph, N., Mann, B., Askell, A., Bai, Y., Chen, A., Conerly, T., DasSarma, N., Drain, D., Ganguli, D., Hatfield-Dodds, Z., Hernandez, D., Jones, A., Kernion, J., Lovitt, L., Ndousse, K., Amodei, D., Brown, T., Clark, J., Kaplan, J., McCandlish, S., and Olah, C.  A mathematical framework for transformer circuits.  _Transformer Circuits Thread_ , 2021.  URL https://transformer-circuits.pub/2021/framework/index.html.
  * Ensign et al. (2024) Ensign, D., Paulo, G., and Garriga-alonso, A.  Ophiology (or, how the mamba architecture works), 2024.  URL https://www.lesswrong.com/posts/TYLQ8gAMAmpeFcwXN/ophiology-or-how-the-mamba-architecture-works.  Accessed: 2024-04-09.
  * Fu et al. (2023) Fu, D. Y., Dao, T., Saab, K. K., Thomas, A. W., Rudra, A., and Ré, C.  Hungry hungry hippos: Towards language modeling with state space models, 2023.
  * Gao et al. (2020) Gao, L., Biderman, S., Black, S., Golding, L., Hoppe, T., Foster, C., Phang, J., He, H., Thite, A., Nabeshima, N., Presser, S., and Leahy, C.  The Pile: An 800gb dataset of diverse text for language modeling.  _arXiv preprint arXiv:2101.00027_ , 2020.
  * Geiger et al. (2021) Geiger, A., Lu, H., Icard, T., and Potts, C.  Causal abstractions of neural networks, 2021.  URL https://arxiv.org/abs/2106.02997.
  * Goldowsky-Dill et al. (2023) Goldowsky-Dill, N., MacLeod, C., Sato, L., and Arora, A.  Localizing model behavior with path patching, 2023.
  * Grazzi et al. (2024) Grazzi, R., Siems, J., Schrodi, S., Brox, T., and Hutter, F.  Is mamba capable of in-context learning?, 2024.
  * Gu & Dao (2023) Gu, A. and Dao, T.  Mamba: Linear-time sequence modeling with selective state spaces, 2023.
  * Gu et al. (2020) Gu, A., Dao, T., Ermon, S., Rudra, A., and Re, C.  Hippo: Recurrent memory with optimal polynomial projections, 2020.
  * Gu et al. (2022) Gu, A., Goel, K., and Ré, C.  Efficiently modeling long sequences with structured state spaces, 2022.
  * Hanna et al. (2023) Hanna, M., Liu, O., and Variengien, A.  How does gpt-2 compute greater-than?: Interpreting mathematical abilities in a pre-trained language model, 2023.
  * Heimersheim & Janiak (2023) Heimersheim, S. and Janiak, J.  A circuit for Python docstrings in a 4-layer attention-only transformer, 2023.  URL https://www.alignmentforum.org/posts/u6KXXmKFbXfWzoAXn/a-circuit-for-python-docstrings-in-a-4-layer-attention-only.
  * Kaplan et al. (2020) Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D.  Scaling laws for neural language models, 2020.
  * Lieber et al. (2024) Lieber, O., Lenz, B., Bata, H., Cohen, G., Osin, J., Dalmedigos, I., Safahi, E., Meirom, S., Belinkov, Y., Shalev-Shwartz, S., Abend, O., Alon, R., Asida, T., Bergman, A., Glozman, R., Gokhman, M., Manevich, A., Ratner, N., Rozen, N., Shwartz, E., Zusman, M., and Shoham, Y.  Jamba: A hybrid transformer-mamba language model, 2024.
  * Mallen et al. (2024) Mallen, A., Brumley, M., Kharchenko, J., and Belrose, N.  Eliciting latent knowledge from quirky language models, 2024.
  * Marks et al. (2024) Marks, S., Rager, C., Michaud, E. J., Belinkov, Y., Bau, D., and Mueller, A.  Sparse feature circuits: Discovering and editing interpretable causal graphs in language models, 2024.
  * Meng et al. (2023) Meng, K., Bau, D., Andonian, A., and Belinkov, Y.  Locating and editing factual associations in gpt, 2023.  URL https://arxiv.org/abs/2202.05262.  Accessed: 2024-7-8.
  * Michel et al. (2019) Michel, P., Levy, O., and Neubig, G.  Are sixteen heads really better than one?  In Wallach, H. M., Larochelle, H., Beygelzimer, A., d’Alché-Buc, F., Fox, E. B., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pp. 14014–14024, 2019.  URL https://proceedings.neurips.cc/paper/2019/hash/2c601ad9d2ff9bc8b282670cdd54f69f-Abstract.html.
  * Nanda & Bloom (2022) Nanda, N. and Bloom, J.  Transformerlens.  https://github.com/TransformerLensOrg/TransformerLens, 2022.
  * Nanda et al. (2023) Nanda, N., Rajamanoharan, S., Kramár, J., and Shah, R.  Fact finding: Do early layers specialise in local processing? (post 5), 2023.  URL https://www.lesswrong.com/posts/xE3Y9hhriMmL4cpsR/fact-finding-do-early-layers-specialise-in-local-processing.  Accessed: 2023-12-22.
  * Olah (2022) Olah, C.  Mechanistic interpretability, variables, and the importance of interpretable bases.  https://www.transformer-circuits.pub/2022/mech-interp-essay, 2022.
  * Olsson et al. (2022) Olsson, C., Elhage, N., Nanda, N., Joseph, N., DasSarma, N., Henighan, T., Mann, B., Askell, A., Bai, Y., Chen, A., et al.  In-context learning and induction heads, 2022.  URL https://transformer-circuits.pub/2022/in-context-learning-and-induction-heads/index.html.
  * Paulo et al. (2024) Paulo, G., Marshall, T., and Belrose, N.  Does transformer interpretability transfer to rnns?, 2024.
  * Pearl (2009) Pearl, J.  _Causality_.  Cambridge University Press, 2 edition, 2009.  ISBN 978-0-521-89560-6.  doi: 10.1017/CBO9780511803161.
  * Peng et al. (2023) Peng, B., Alcaide, E., Anthony, Q., Albalak, A., Arcadinho, S., Biderman, S., Cao, H., Cheng, X., Chung, M., Grella, M., GV, K. K., He, X., Hou, H., Lin, J., Kazienko, P., Kocon, J., Kong, J., Koptyra, B., Lau, H., Mantri, K. S. I., Mom, F., Saito, A., Song, G., Tang, X., Wang, B., Wind, J. S., Wozniak, S., Zhang, R., Zhang, Z., Zhao, Q., Zhou, P., Zhou, Q., Zhu, J., and Zhu, R.-J.  Rwkv: Reinventing rnns for the transformer era, 2023.  URL https://arxiv.org/abs/2305.13048.
  * Radford et al. (2019) Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I.  Language models are unsupervised multitask learners.  2019\.
  * Rimsky et al. (2024) Rimsky, N., Gabrieli, N., Schulz, J., Tong, M., Hubinger, E., and Turner, A. M.  Steering llama 2 via contrastive activation addition, 2024.
  * Sharma et al. (2024) Sharma, A. S., Atkinson, D., and Bau, D.  Locating and editing factual associations in mamba, 2024.
  * Sundararajan et al. (2017) Sundararajan, M., Taly, A., and Yan, Q.  Axiomatic attribution for deep networks, 2017.
  * Syed et al. (2023) Syed, A., Rager, C., and Conmy, A.  Attribution patching outperforms automated circuit discovery, 2023.
  * Torres (2024) Torres, A.  Othello Mamba: Evaluating the mamba architecture on the othellogpt experiment, 2024.  URL https://github.com/alxndrTL/othello_mamba.
  * Wang et al. (2023) Wang, K. R., Variengien, A., Conmy, A., Shlegeris, B., and Steinhardt, J.  Interpretability in the wild: a circuit for indirect object identification in GPT-2 small.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=NpsVSN6o4ul.
  * Wei et al. (2022) Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D., Chi, E. H., Hashimoto, T., Vinyals, O., Liang, P., Dean, J., and Fedus, W.  Emergent abilities of large language models, 2022.
  * Zhang & Nanda (2024) Zhang, F. and Nanda, N.  Towards best practices of activation patching in language models: Metrics and methods, 2024.

Figure 10:  Displayed is 1 - (Normalized logit diff) for each (layer,
position) patch, averaged over 80 data points. 0 corresponds to acting like
the uncorrupted forward pass, and 1 corresponds to acting like the corrupted
forward pass. The y-axis is Layer, and the x-axis is token position. The
corruptions can be observed by inspecting the token position labels. Each of
the five plots correspond to different IOI patches. Figure 11:  Same as Figure
10, but for blocks.{layer}.hook_proj_out

##  Appendix A IOI Task Details

We use the 4 prompt templates from (Conmy et al., 2023):

    Then, [NAME], [NAME] and [NAME] went to
    the [PLACE]. [NAME] and [NAME] gave a
    [OBJECT] to

    Afterwards [NAME], [NAME] and [NAME]
    went to the [PLACE]. [NAME] and [NAME]
    gave a [OBJECT] to

    When [NAME], [NAME] and [NAME] arrived
    at the [PLACE], [NAME] and [NAME] gave
    a [OBJECT] to

    Friends [NAME], [NAME] and [NAME] went
    to the [PLACE]. [NAME] and [NAME] gave
    a [OBJECT] to

In resample ablation, there are many ways to corrupt a prompt. We create a
dataset choosing randomly from all possible corruptions and locations of names
that:

  1. 1.

Replace all instances of a single name with another name, and

  2. 2.

Change the output

While we could patch two names at the same time, 1 simplifies the number of
things being changed at the same time. 2 is necessary to determine if the
patch had any effect.

This results in the following 5 corruptions:

    CAB AB C
    DAB AB D

    ACB AB C
    ADB AB D

    ABC AB C
    ABD AB D

    ABC AB C
    ABC AC B

    ABC AC B
    ABC BC A

In each of these, the top line represents the uncorrupted prompt, and the
bottom line represents the corrupted prompt. Letters correspond to names: the
first three are the first three names, the second two are the fourth and fifth
names, and the last is the output. If two letters are the same, that means
that those places share the same name. Otherwise, the names are different.

##  Appendix B Normalized Logit Diff

Normalized Logit Diff is defined as:

    min_diff =
        A_logit_corrupted - B_logit_corrupted
    max_diff =
        A_logit_unpatched - B_logit_unpatched
    possible_range = abs(max_diff - min_diff)
    # prevent divide by zero
    possible_range[possible_range == 0] = 1
    logit_diff =
        A_logits_patched - B_logits_patched
    normalized_logit_diff =
        (logit_diff-min_diff)/possible_range

where

  * •

unpatched is a forward pass without our intervention (the baseline forward
pass)

  * •

corrupted is a forward pass without our intervention, where the prompt is
modified to make $B$ the correct answer

  * •

patched is a forward pass that patches edges (as described above)

This results in a 1 when the model acts like the unpatched forward pass, and 0
when the model acts like the corrupted forward pass. Note that it is possible
to obtain scores outside the [0,1] range.

The abs is a novel addition by us. For data points where the model is
incorrect, maximizing normalized logit diff would result in the model becoming
more incorrect. This abs modification fixes that issue.

##  Appendix C SSM Hooks used

For the cosine similarity plots, we used blocks.39.hook_B_bar,
blocks.39.hook_ssm_input, and blocks.39.hook_h.{pos}

See figure 12 for a detailed overview of the SSM nternals.

Figure 12: Internals of the SSM block, we restrict this diagram to only the
parts we are interested in

##  Appendix D Automated Circuit Discovery Results

We use the following edges:

  * •

embed $\mapsto$ layer input (hook_embed $\mapsto$ blocks.i.hook_layer_input)

  * •

layer output $\mapsto$ later layer input (blocks.i.hook_proj_out $\mapsto$
blocks.j.hook_layer_input)

  * •

layer output $\mapsto$ output (blocks.i.hook_proj_out $\mapsto$
blocks.47.hook_resid_post)

  * •

embed $\mapsto$ output hook_embed $\mapsto$ blocks.47.hook_resid_post)

Where output is the residual stream after the final layer has added its layer
output.

We do a few separate experiments.

###  D.1 EAP

At the most high level, we can run (integrated gradient) EAP without
positions. Using binary search to find the minimum number of edges to give us
at least 85% accuracy results in the following adjacency matrix:

Figure 13: Integrated gradients EAP, minimum set of edges. A blue dot means
the edge is present. The y-axis is the input node, the x-axis is the output
node

We also present the edge attributions here, and the corresponding actual
effects on normalized logit diff (determined during the ACDC run below)

Figure 14: Edge Attributions

Figure 15: Effects on normalized logit diff

This is not very insightful, so we clamp values to let us see more (the
thresholds chosen by hand)

###  D.2 ACDC for layer information

We run EAP without positions using the edges listed above, and use binary
search to find the least edges needed to get 85% accuracy. We take the
resulting graph and run ACDC on it with a thresh of 0.0001, with (non-
positional) edges for individual conv slices, the ssm, the skip connection,
and all the edges above.

This allows us to get a hint at what parts each layer is using.

Figure 16: ACDC results from inside layers. Each node is 1 if the edge is
present, 0 if it is not. 0,-1, and -2 are the corresponding conv slices Figure
17: Same as the above figure, however, each cell shows the decrease in
normalized logit diff if that edge is patched Figure 18: Same as above,
however, values are clamped to 0.1 Figure 19: Same above, however, values are
clamped to 0.05

This resulting circuit has an average normalized logit diff of 0.84 and
achieves 88% accuracy on a held-out test set, so there is little loss in
performance from doing this further prune (because the thresh is so low, most
edges pruned are those that decrease ability to do the task, which is why
accuracy has gone up).

Of note, this reproduces the “Convs of layer 39 shift names to the next
position” result from above.

Ideally we could do this with EAP and no longer need ACDC, but but leave that
for future work.

###  D.3 EAP With Positions

In the following:

  * •

n1 means the first name in the prompt, n2 means the second name in the prompt,
etc.

  * •

pos0 means the first token, pos1 means the second token, etc. (these are used
for non-name tokens)

  * •

out means the final token, where the answer is generated

For reference, here is a prompt:

    pos0 <|endoftext|>
    pos1 Then
    pos2 ,
    n1 Sally
    pos4 ,
    n2 Martha
    pos6 and
    n3 Edwin
    pos8 went
    pos9 to
    pos10 the
    pos11 restaurant
    pos12 .
    n4 Edwin
    pos14 and
    n5 Sally
    pos16 gave
    pos17 a
    pos18 drink
    out to

####  D.3.1 Connections from embed

Every layer receives n1-n5, except:

    Missing n1: layers 1, 5, 8, 25, 28, 29,
         30, 32, 34, 36
    Missing n2: 30, 31, 36
    Missing n3: layers 25, 27, 29, 30, 31,
         34, 36, 38
    Missing n4: layers 3, 9, 25, 32, 34, 40
    Missing n5: layer 9, 25, 27, 31, 34, 37,
         38, 40
    Missing n1-n5: 33, 41-47
    TODO: Output?

####  D.3.2 Connections of Layer 0

Layer 0 takes as input n1-n5, and sends n1-n5 to every layer, except:

    Missing n1: 1, 2, 3, 28, 31, 32, 33, 34
    Missing n2: 6, 7, 31, 33
    Missing n3: 2, 31, 33
    Missing n4: 1, 2, 3, 9, 18, 21, 32, 34, 40
    Missing n5: 3, 9, 18, 31, 32, 34, 40
    Missing n1-n5: 4, 5, 41-47

####  D.3.3 Layers that are missing names

If we consinder a layer as “having” a name if it received it from embed or
layer 0, the following layers have n1-n5:

And these are ones that are missing names:

    Missing n1: 1, 5, 28, 32, 33, 34
    Missing n2: 31, 33
    Missing n3: 31, 33
    Missing n4: 32, 34, 3, 40, 9
    Missing n5: 9, 31, 34, 40
    Missing n1-n5: 41-47

Of those, 1, 3, 5, 9 are only connected to 0/embed and 39. In particular, we
have:

    1: missing n1
       n1,n2,n3,n5 -> 39
    3: missing n4
       n1-n5 -> 39
    5: missing n1
       n1-n5 -> 39
    9: missing n4,n5
       n1-n5 -> 39

Otherwise, we have

    Missing n1: 28, 32, 33, 34
    Missing n2: 31, 33
    Missing n3: 31, 33
    Missing n4: 32, 34, 40
    Missing n5: 31, 34, 40
    Missing n1-n5: 41-47

28, 31, 32, 33, 34, 40 all seem to be involved in a complex circuit, and have
inputs from other layers.

Just examining the missing terms:

    28 is missing n1

    28 does not receive n1 from anyone
        outputs n1 to 39

    31 is missing n2, n3, n5

    31 does not receive n2 or n3 from anyone
        output n2-n3 to 39
    31 receives n5 from 29
        outputs n5 to 34

    32 is missing n1, n4

    32 does not receive n1
       outputs n1 to 39
    32 receives n4 from 28, 30
       outputs n4 to 34

    33 is missing n1-n3

    33 does not receive n1-n3
       outputs n2-n3 to 39
       outputs n1 to 35

    34 is missing n1, n4, n5

    34 does not receive n1 from anyone
        outputs n1 to 39

    34 receives n4 from 32
        does not output it

    34 receives n5 from 28, 31
        does not output it

    40 is missing n4, n5

    40 does not receive n4-n5
        does not output n4-n5

####  D.3.4 Connections to 39

As expected, layer 39 stands out as noteworthy. Every layer before 39 has a
connection to 39 for every name, with these exceptions:

    Missing n1: layer 2
    Missing n2: layer 34
    Missing n3: layer 34
    Missing n4: layers 1, 31, 32, 34
    Missing n5: layers 2, 31, 32, 34

In addition, there are these extra connections to layer 39

    pos6: layer 34
    pos14: layers 31, 32, 34
    out: layers  28, 29, 30, 33, 35, 37, 38

Where

  * •

pos6 is the “ and” between n2 and n3

  * •

pos14 is the “ and” between n4 and n5

####  D.3.5 Connections from 39

    n1,n2,n3: layer 40
    pos12: layer 43
    pos14: layer 40
    pos16: layers 40,41,43,44,45,46,47
    pos18: layer 40
    out: layers 43,45,46,47, and output

  * •

pos12 is the “.”

  * •

pos14 is the “ and” between n4 and n5

  * •

pos16 is the “ gave” after n5

  * •

pos18 is the object (for example, “ drink”)

####  D.3.6 Graph after hiding 39, embed, and 0

Keeping the above in mind, once we hide those three nodes the graph is quite
readable. If we hide 35, it is even more readable. We also plot layer 35, for
reference.

Figure 20: Positional EAP After hiding Embed, Layer 0, and Layer 39. Numbers
correspond to names, pos14 means token in position 14, out means the final
token Figure 21: Same as above, but also hide 35 Figure 22: Layer 35
Positional EAP results