# Grokking Group Multiplication with Cosets

Dashiell Stander  Qinan Yu  Honglu Fan  Stella Biderman

###### Abstract

We use the group Fourier transform over the symmetric group $S_{n}$ to reverse
engineer a 1-layer feedforward network that has ”grokked” the multiplication
of $S_{5}$ and $S_{6}$. Each model discovers the true subgroup structure of
the full group and converges on circuits that decompose the group
multiplication into the multiplication of the group’s conjugate subgroups. We
demonstrate the value of using the symmetries of the data and models to
_understand_ their mechanisms and hold up the “coset circuit” that the model
uses as a fascinating example of the way neural networks implement
computations. We also draw attention to current challenges in conducting
mechanistic interpretability research by comparing our work to Chughtai et al.
[6] which alleges to find a different algorithm for this same problem.

Machine Learning, Grokking, Mechanistic Interpretability, Group Theory,
Harmonic Analysis

##  1 Introduction

The program of modern mechanistic interpretability was first clearly
articulated in [44]: deep neural networks use directions in neuron activation
space as features and perform tasks by combining those features in neural
“circuits.” The features that neural networks learn and the circuits that they
form do not have to be opaque. With care and effort researchers can peer into
the black box of deep models and understand _how_ they accomplish the tasks
that they are trained to accomplish.

We follow prior work in circuit-level mechanistic interpretability and study a
model and a task that we can understand completely [6, 23, 40, 41]. In so
doing we hope to build an understanding of the the types of features that
neural networks form and the precise mechanisms with which neural networks
combine and transform those features. We hope that by reverse-engineering the
function of each neuron in a model that performs a simple task we will
contribute to a foundation of understanding from which to study the mechanisms
of massive models.

Figure 1: The coset circuit that the model uses to perfectly generalize the
group multiplication. The circuit stores information about coset membership
for the left and right permutations in the embeddings. The linear layer
queries the embeddings and combines the information to determine whether or
not the product is in a specific coset. Coset membership is encoded in the
sign of the activations.

In this paper we return to the subject of Chughtai et al. [6] and analyze one
hidden layer fully connected networks of varying widths that have perfectly
learned the task of group multiplication. We found their analysis incomplete,
however, and build on it by using the full Group Fourier transform to
completely reverse-engineer the most common mechanism converged networks use
to implement group multiplication. Though there are in fact many different
neural circuits that the networks form, we can describe the vast majority
using the cosets of $S_{n}$ that we refer to as the _coset circuit_. Cosets
are subsets of a group that have specific properties in relation to each other
that the model can use to perfectly generalize in the task of group
multiplication (see Section 3.1 for concrete examples of cosets for
permutation groups or Appendix D for a formal definition).

The high level steps of the coset circuit, given two permutations
$\sigma_{l},\;\sigma_{r}$, are:

  1. 1.

In the left and right embedding layers, the model stores information about
membership in dozens of left and right cosets.

  2. 2.

In the linear layer, the embeddings are queried to get the coset membership
for $\sigma_{l}$ and $\sigma_{r}$. The linear layer combines this information
to get the probable coset membership of their product $\sigma_{l}\sigma_{r}$.

  3. 3.

In the unembedding layer, the identity of $\sigma_{l}\sigma_{r}$ is determined
as the only permutation in $S_{n}$ that satisfies all of the different coset
memberships computed by the linear layer in step 2.

###  1.1 Our Contributions

Our main contributions are as follows:

  1. 1.

We completely reverse engineer a 1-hidden layer fully-connected network
trained on the permutation groups $S_{5}$ and $S_{6}$.

  2. 2.

We present a novel application of the Group Fourier Transform to circuit-level
mechanistic interpretability.

  3. 3.

We apply a methodology inspired by Geiger et al. [21] to use causal
interventions thoroughly test all of the properties of our proposed circuit.

  4. 4.

We survey current research in mechanistic interpretability and draw
connections between the difficulty of our work and broader challenges in the
field.

##  2 Related Work

Mechanistic Interpretability We analyze the mechanisms of neural networks at
the _circuit level_ of individual and small groups of neurons, drawing
directly on the work of [40, 41, 45, 59]. Our work builds directly on “A Toy
Model of Universality” by Chughtai et al. [6]. We recreated precisely their
experimental setup for the groups $S_{5}$ and $S_{6}$, but found their
analysis incomplete and could not find a mechanism implementing their proposed
“Group Composition via Representations” algorithm. For a thorough comparison
of our work and [6], see Appendix F.

Grokking Our choice of studying models trained on small permutation groups was
made in no small part because of the appearance of “grokking,” wherein the
model first memorizes a training set and then much later generalizes to the
held out data perfectly. Grokking was first identified by Power et al. [47]
and has been well studied for its counter-intuitive training dynamics [31, 38,
52, 49, 57, 56]. We conducted all the analysis on fully grokked models with
perfect test accuracy.

Group Theory Our analysis owes much to the seminal monograph “Group
Representations in Probability and Statistics” [12] and the varied literature
building on it [8, 30, 29, 26, 28]. We implement in Pytorch the Fast Fourier
transform algorithm over the symmetric group $S_{n}$ developed by Clausen &
Baum [7]. Our implementation is heavily inspired by the example in Julia of
Plumb et al. [46].

##  3 Background

###  3.1 Permutations and the Symmetric Group

In this section we will give a concrete exposition of some concepts of group
theory as they are concretely realized in the permutation groups that we
study. For a more formal introduction to group theory, please refer to
Appendix D.

A permutation of $n$ elements is a map $\sigma$ that sends one ordering of the
$n$ elements to a different ordering, for example the order-reversing
permutation on four elements would be:

$(1\;2\;3\;4)\stackrel{{\scriptstyle\sigma}}{{\mapsto}}(4\;3\;2\;1)$

and the identity permutation, denoted $e$, changes nothing:

$(1\;2\;3\;4)\stackrel{{\scriptstyle e}}{{\mapsto}}(1\;2\;3\;4)$

We write specific permutations by identifying them with the image of their
action on the elements $\\{1,2,\dots,n\\}$ in their standard order. For the
above example, we would simply denote the order reversing permutation on four
elements as $(4\;3\;2\;1)$.

We multiply two permutations on $n$ elements $\sigma,\tau$ by composition,
read from right to left. If $\sigma=(4\;3\;2\;1)$ and $\tau=(3\;2\;1\;4)$,
then $\sigma\tau$ is the permutation we obtain by first applying $\tau$ and
then applying $\sigma$:

$(1\;2\;3\;4)\stackrel{{\scriptstyle\tau}}{{\mapsto}}(3\;2\;1\;4)\stackrel{{\scriptstyle\sigma}}{{\mapsto}}(4\;1\;2\;3)$

What we see is that first applying $\tau$ and then $\sigma$ has the same
effect as just applying the permutation $(4\;1\;2\;3)$. Additionally every
permutation $\sigma$ has an inverse $\sigma^{-1}$ such that
$\sigma\sigma^{-1}=e$. These properties makes all of the permutations on $n$
elements a _group_ called the symmetric group, which we write $S_{n}$.

There are six permutations in $S_{4}$ that ”fix” $4$:

$\begin{matrix}(1\;2\;3\;4)&(2\;1\;3\;4)&(3\;2\;1\;4)\\\
(1\;3\;2\;4)&(3\;1\;2\;4)&(2\;3\;1\;4)\end{matrix}$

These six permutations form a _subgroup_ of $S_{4}$ because multiplying any
two permutations that fix four results in another permutation that fixes four.
You can see that these six permutations are homomorphic to $S_{3}$ by simply
“forgetting” about the $4$ that is fixed in the fourth position.

If we take a subgroup such as the copy of $S_{3}<S_{4}$ that fixes four and
multiply every element of that subgroup on the left by some element $\sigma\in
S_{4}$ then we get a _left coset_ of $S_{3}$ denoted $\sigma S_{3}$. The
transposition $\tau=(4\;2\;3\;1)$ switches the elements in the first and
fourth positions. The elements of $\tau S_{3}$ are:

$\begin{matrix}(4\;2\;3\;1)&(4\;1\;3\;2)&(4\;2\;1\;3)\\\
(4\;3\;2\;1)&(4\;1\;2\;3)&(4\;3\;1\;2)\end{matrix}$

This coset is characterized by every element having $4$ in the first position,
because $\tau$ switches positions the first and fourth positions and $S_{3}$
always has $4$ in the fourth position. We would get a coset with all of the
elements of $S_{4}$ with $4$ in the third position if we multiplied $S_{3}$
the left by the transposition that switches three and four.

There are also _right cosets_ where every element in a subgroup is multiplied
from the right. The elements of $S_{3}\tau$ are:

$\begin{matrix}(4\;2\;3\;1)&(1\;4\;3\;1)&(3\;2\;4\;1)\\\
(4\;3\;2\;1)&(3\;4\;2\;1)&(2\;3\;4\;1)\end{matrix}$

This right coset is characterized by every element having $1$ in the fourth
position, because $S_{3}$ fixes the element in the fourth position and $\tau$
has $1$ in the fourth position.

There are in fact four subgroups of $S_{4}$ that are isomorphic to $S_{3}$:
one where each element $\\{1,\dots,4\\}$ is fixed. In general there are $n$
subgroups of $S_{n}$ that are isomorphic to $S_{n-1}$. These different
“copies” of $S_{3}<S_{4}$ are all _conjugate_ to each other. Conjugation by an
element $\sigma$ maps $x\mapsto\sigma x\sigma^{-1}$. So if we have the $S_{3}$
that we have been working with that fixes $4$ and conjugate by
$\sigma=(1\;4\;3\;2)$, then $\sigma S_{3}\sigma^{-1}$ is the copy of $S_{3}$
that fixes $2$:

$\begin{matrix}(1\;2\;3\;4)&(3\;2\;1\;4)&(4\;2\;3\;1)\\\
(1\;2\;4\;3)&(4\;2\;1\;3)&(3\;2\;4\;1)\end{matrix}$

If a subgroup is invariant to conjugation then it is a _normal_ subgroup. The
only normal subgroup of $S_{n}$ for $n>4$ is the _alternating group_ $A_{n}$
of even permutations.

A transposition is a permutation $\tau\in S_{n}$ that switches (“transposes”)
two elements $i,j\in[n]$ and leaves the remaining elements fixed. Every
element of $S_{n}$ can be decomposed into a product of transpositions. For a
given permutation this decomposition is not unique, but the number of
transpositions in the decomposition is constant. The permutations that have an
even number of transpositions are referred to as “even” permutations and those
with an odd number are “odd.” $A_{n}$ is made up of the permutations that have
an even number of transpositions. For normal subgroups the left and right
subgroups are equal, so $\sigma A_{n}=A_{n}\sigma$.

We will mostly refer to groups by name, but we will denote a general group as
capital $G$ and a general subgroup as $H\leq G$. For a proper subgroup ($H\neq
G$), we will write $H<G$. For a normal subgroup, we will use $N\trianglelefteq
G$.

Figure 2: Model Architecture: we follow the model architecture used by [6].
The one-hot vectors of left and right permutations pass through separate
embeddings. We concatenate the embeddings and pass them through a single
fully-connected hidden layer with ReLU activations. An unembedding matrix
transforms the activations into logits.

###  3.2 Fourier Transform over Groups

The Discrete Fourier Transform (DFT) converts a function $f$ defined on
$\\{0,1,\dots,n-1\\}$ to a complex-valued function via the formula:

$\hat{f}(k)=\sum_{t=0}^{n-1}f(t)e^{-2i\pi kt/n},\quad k\in\\{0,\dots,n-1\\}$

The DFT is commonly interpreted as a conversion from the _time_ domain to the
_frequency_ domain because the $e^{-2i\pi kt/n}$ terms define a complex
sinusoid with frequency $2\pi kt/n$. The frequency domain in this case means
that these frequencies provide an alternative orthonormal basis from which we
can work with functions. A function on $\\{0,1,\dots,n-1\\}$ can be
represented as a vector
$f=\begin{pmatrix}x_{0}&x_{1}&\dots&x_{n-1}\end{pmatrix}^{\top}$ and its basis
is given by the identity matrix $I_{n}$. The DFT defines a basis
transformation, much like any other. The Fourier basis is given $n$ vectors.
The first basis vector, corresponding to $k=0$, is all ones. The $k=1$ basis
vector is
$\begin{pmatrix}1&e^{-2i\pi/n}&\dots&e^{-2i\pi(n-1)/n}\end{pmatrix}$, and all
of the rest for up to $n\\!-\\!1$ are given by $\begin{pmatrix}1&e^{-2i\pi
k/n}&\dots&e^{-2i\pi(n-1)k/n}\end{pmatrix}$.

This basis has a number of useful properties, that stem from how well-fit it
is to the structure of the domain. There are many functions that appear
complicated in the time domain that are relatively simple or sparse in the
frequency domain.

The DFT has a particularly nice interpretation as a function on the cyclic
group $C_{n}$, which is isomorphic to addition modulo $n$. Please refer to
Appendix D or to references such as [12, 19, 30] for a more detailed
discussion.

The interpretation of the DFT as being over the cyclic groups can be
generalized to non-commutative groups. We go over the construction in Appendix
D.6 and E. The high level interpretation, however, is the same. For functions
from $S_{n}\rightarrow\mathbb{C}$ there is an orthonormal basis that is
equivariant to translations and convolutions. The frequencies for the Fourier
transform over $S_{n}$ are given by the partitions of $n$. The “highest”
frequencies can be interpreted as representing functions that are constant on
permutations that all agree on a small number of elements of $[n]$ [16].

##  4 Model Architecture

We study a fully connected feed-forward network that is trained to learn the
multiplication of finite permutation groups. As shown in Figure 2, the model
contains separate left and right embeddings, followed by a fully connected
linear layer with ReLU activations, and an unembedding layer.

  * •

One hot vectors $\mathbf{x}_{g}$ with length $|G|$.

  * •

Two embedding matrices, $\mathbf{E}_{l},\;\mathbf{E}_{r}$ with dimensions
$(d,\;|G|)$, where $d$ is embedding dimension.

  * •

A linear layer $\mathbf{W}$ with dimension $(w,\;2d)$, $w$ denoting the width
of the linear layer. After the linear layer we apply the ReLU pointwise
nonlinearity.

  * •

An unembedding layer $\mathbf{U}$ with dimension $(|G|,\;w)$, which transforms
the outputs of the ReLU and linear layer to into logit space for the group.

We also note that the first $d$ columns of the linear layer will only act on
the left embeddings and the second $d$ columns will only act on the right
embeddings, so we can analyze $\mathbf{W}$ as the concatenation of two
$(w,\;d)$ matrices: $\mathbf{W}=[\mathbf{L}\;\mathbf{R}]$.

$\mathbf{W}\begin{bmatrix}\mathbf{E}_{l}\mathbf{x}_{g}\\\
\mathbf{E}_{r}\mathbf{x}_{h}\end{bmatrix}=\mathbf{L}\mathbf{E}_{l}\mathbf{x}_{g}+\mathbf{R}\mathbf{E}_{r}\mathbf{x}_{h}$

##  5 Coset Circuits

In this section we will describe the precise mechanism of the _coset circuits_
that the models use to implement multiplication in $S_{5}$ and $S_{6}$.

First in Section 5.1 we will describe how in the linear layer the simplest
circuit, the ”Sign Circuit,” implements the multiplication of the two cosets
of the alternating group $A_{n}$.

In Section 5.2 we will describe how the linear layer uses coset information
with _conjugate_ subgroups such as $S_{4}<S_{5}$.

And in Section C.3 we discuss the distribution of different circuits and
subgroups that the model converges on over many different runs.

###  5.1 Sign Circuit

(a) Weight Analysis in Fourier Basis (Left)

(b) Weight Analysis in Fourier Basis (Right)

(c) Activations of all permutations combinations pre-relu

(d) Activations of all permutations combinations post-relu

Figure 3: Four subfigures in two subgroups

The even permutations form a subgroup called the alternating group $A_{n}$.
$A_{n}$ has two cosets: the group itself $A_{n}$ and all of the odd
permutations $\tau A_{n}$. The sign map $\operatorname{sgn}$ is given by:

$\operatorname{sgn}(\sigma)=\begin{cases}1\quad\sigma\in A_{n}\\\
-1\quad\sigma\in\tau A_{n}\end{cases}$

The sign map respects multiplication in $S_{n}$. For any $\sigma,\rho\in
S_{n}$, the sign of their product is the product of their signs:
$\operatorname{sgn}(\sigma\rho)=\operatorname{sgn}(\sigma)\operatorname{sgn}(\rho)$.

There are three steps to each neuron’s mechanism. In what follows, $x$ is the
magnitude of the pre-activation, $\sigma$ refers to a permutation, and the
subscripts $l,r,t$ on $\sigma$ either refer to the left input permutation, the
right input permutation, or the target permutation
$\sigma_{t}=\sigma_{l}\sigma_{r}$, respectively.

  1. 1.

The neuron weights corresponding to the left and right permutations “read off”
the pre-activations from the embeddings. The pre-activations for the left and
right take on one of two values: $x\operatorname{sgn}(\sigma)$ or
$-x\operatorname{sgn}(\sigma)$.

  2. 2.

The left and right pre-activations are added together through linear layer, so
that the full pre-activations now take on one of three values: $-2x$, $0$, or
$2x$.

  3. 3.

The ReLU activation function cuts off the pre-activations if they are $-2x$
and otherwise passes them along unchanged to the unembedding layer.

Let us take as a concrete example the neuron shown in Fig. 3, where the left
pre-activations $L(\sigma)=-\operatorname{sgn}(\sigma)x$ and the right pre-
activations $R(\sigma)=\operatorname{sgn}(\sigma)x$. The full action of the
neuron is given by $\max(0,L(\sigma_{l})+R(\sigma_{r})$ and there are three
cases:

  1. 1.

$\operatorname{sgn}(\sigma_{l})=\operatorname{sgn}(\sigma_{r})\Rightarrow\operatorname{sgn}(\sigma_{l}\sigma_{r})=1$.
In this case $L(\sigma_{l})$ and $R(\sigma_{r})$ destructively interfere,
cancelling out to $0$. Both the pre-activation and activation are $0$.

  2. 2.

$\operatorname{sgn}(\sigma_{l})=-1,\;\operatorname{sgn}(\sigma_{r})=1\Rightarrow\operatorname{sgn}(\sigma_{l}\sigma_{r})=-1$.
In this case $L(\sigma_{l})$ and $R(\sigma_{r})$ reinforce each other and sum
to a positive value. Since $2x>0$, the activation value is $2x$.

  3. 3.

$\operatorname{sgn}(\sigma_{l})=1,\;\operatorname{sgn}(\sigma_{r})=-1\Rightarrow\operatorname{sgn}(\sigma_{l}\sigma_{r})=-1$.
Like in (2) the product $\sigma_{l}\sigma_{r}$ is an odd permutation and
$L(\sigma_{l})$ and $R(\sigma_{r})$ constructively interfere, though this time
$L(\sigma_{l})+R(\sigma_{r})=-2x<0$. Thus ReLU clips the pre-activation and
sends it to $0$, so despite the information that $\sigma_{l}\sigma_{r}$ is
even is present in the pre-activations, the activation that gets passed to the
unembedding layer is identical to an even permutation as in (1).

###  5.2 Conjugate Subgroup Circuit

All four ways to multiply two cosets of $A_{n}$ are well-defined. For each of
the four options (even-even, odd-even, etc…) we know which coset of $A_{n}$
the product will be in, but no other subgroup of $S_{n}$ has this property.
What they have are other conjugate subgroups. The model learns to identify
those subgroups using the fact that the coset multiplication is well-defined
for specific pairs of conjugate subgroups. In table 1 we provide the coset
multiplication table for two subgroups of $S_{5}$ that we will refer to as
$H_{1}$ and $H_{5}$. Both are isomorphic to $S_{4}$, $H_{1}$ fixes $1$ and
$H_{5}$ fixes $5$. They are related by conjugation. The transposition
$\tau_{(15)}$ sends one subgroup to the other:
$\tau_{(15)}H_{1}\tau_{(15)}=H_{5}$ and $\tau_{(15)}H_{5}\tau_{(15)}=H_{1}$.

Far from being fully defined for every combination, every right coset of
$H_{5}$ has precisely one paired left coset of $H_{1}$ that produces the coset
$H_{1}\tau_{(15)}$. $H_{1}\tau_{(15)}$ has 24 elements, but the because of the
double coset structure of

Despite this being more complicated for us to reason about than the $A_{5}$
case, the neural network treats these cases the same. There are pairs of
subgroups that have a predictable multiplication, for a specific neuron the
model learns features so that the pre-activations of the predictable products
precisely cancel out to zero, and when that neuron fires the models knows that
the product is _not_ in the coset that neuron is specialized to predict.

| $H_{1}$ | $\tau_{(12)}H_{1}$ | $\tau_{(13)}H_{1}$ | $\tau_{(14)}H_{1}$ | $\tau_{(15)}H_{1}$
---|---|---|---|---|---
$H_{5}$ |  |  |  |  | $\tau_{(15)}H_{1}$
$H_{5}\tau_{(15)}$ | $\tau_{(15)}H_{1}$ |  |  |  |
$H_{5}\tau_{(25)}$ |  | $\tau_{(15)}H_{1}$ |  |  |
$H_{5}\tau_{(35)}$ |  |  | $\tau_{(15)}H_{1}$ |  |
$H_{5}\tau_{(45)}$ |  |  |  | $\tau_{(15)}H_{1}$ |
Table 1: Coset multiplication table for $H_{1},H_{5}$ where
$H_{i}\coloneqq\\{\sigma\in S_{5}|\;\sigma(i)=i\\}$. The coset
$\tau_{(15)}H_{1}$ corresponds to all of the permutations in $S_{5}$ with $1$
in the fifth position. If the space is left blank, then multiplication of
those two cosets creates every element of $S_{5}$ _not_ in $\tau_{(15)}H_{1}$.

###  5.3 Decoding Permutations with Coset Membership

Figure 4: An example of an $S_{4}<S_{5}$ coset circuit bit pattern for the
permutation $(5\;4\;3\;2\;1)$. The value of each position of the permutation
is encoded in five coset circuits, twenty-five in total. Highlighted is the
code for the third position. The value is $3$ because three is the only
circuit for that position that did _not_ fire. Each individual circuit for a
position-value pair (i.e. a single square in the diagram) will consist of as
few as one or as many as fifteen neurons dedicated. The median number of
neurons involved in a single coset circuit depends on the subgroup, but is
around four. Figure 5: The effect of combining coset circuits. These show the
contributions of one, two, and all four $S_{4}$ coset circuits to the logits
of each permutation when the target permutation is _not_ in $S_{4}$ (when the
target is in $S_{4}$ then none of these neurons fire and their contributions
to the logits is identically zero).

The unembedding layer receives as input a vector of activations from that
encode the coset membership of of the product $\sigma_{l}\sigma_{r}$. Each
element of this vector can best be thought of as an on/off switch keyed to a
specific coset. If the activation is positive then the product
$\sigma_{l}\sigma_{r}$ is certainly not in that coset, but if it is zero it is
only _probably_ in the coset. Putting aside this ambiguity for a moment, we
can see that with enough of these circuits the model can uniquely encode every
permutation $\sigma\in S_{n}$ and perfectly solve the group multiplication.

Take as an example the five subgroups $H_{i}<S_{5}$ that fix the element $i$
and are isomorphic to $S_{4}$. For any pair $(H_{i},\;H_{j})$, including when
$i=j$, there is a double coset consisting of all permutations that have $i$ in
the $j\textsuperscript{th}$ position. As shown in Figure 4, we can associate
five circuits to each position of the product permutation
$\sigma_{l}\sigma_{r}$. The zoomed in portion of Figure 4 shows the five
circuits that correspond to the $3\textsuperscript{rd}$ position. Each circuit
encodes the information “is the value in the $3\textsuperscript{rd}$ position
$i$?” If the circuit fires then the answer to that question is “no,” but there
will always be one circuit of the five that does not fire. Encoded in this
way, the membership in all 25 circuits _uniquely identifies_ every permutation
in $S_{5}$. In general, because the cosets of a subgroup partition the entire
group, if there are $k$ conjugate subgroups of $H\leq G$, then the $k^{2}$
shared cosets will uniquely identify each element of $G$.

The actual single-neuron coset circuits are not perfect on/off switches.
Because of the ReLU half of the time the neuron does not fire (refer to Figure
3(d) and notice the large amount of even permutations with $0$ activation).
The model compensates for this by having multiple neurons dedicated to a
single coset. Figure 5 shows how the unembedding layer aggregates four
distinct $(H_{1},\;H_{1})$ circuits. For each of the neurons the effects on
the final logits is simple: the product $\sigma_{l}\sigma_{r}$ is not in
$H_{1}$, so the the unembedding uses the signal from these neurons to decrease
the logits of all of the permutations in $H_{1}$ and increase the logits of
all of the permutations that are in $H_{1}$. For a single neuron, however,
there is non-trivial overlap between $H_{1}$ and not-$H_{1}$ at $0$. The
mistakes of each individual neuron cancel out when they are all added
together, a single neuron may fail to activate for a permutation, but it is
very unlikely that all four $(H_{1},\;H_{1})$ neurons will fail to fire for
that neuron. As we see in Figure 5, with all four neurons there is minimal
overlap in the logits.

##  6 The Process of Reverse Engineering

In this section, we recite the process of reverse engineering the coset
circuit. First, we observe the activations and build up a theory for their
mechanism. Second, we confirm the sufficiency and necessity of the circuits we
have identified via ablations. Finally, we rigorously validate our hypothesis
by testing the properties of the circuit through causal interchange
interventions.

###  6.1 Identifying Coset Circuits

To do mechanistic interpretability you must spend some time staring at the
weights. The group Fourier transform did, however, give us a place to start
looking. Individual neurons would concentrate entirely on irreducible
representations of $S_{n}$, the “frequencies” of the group Fourier transform.
It was as if the activations of each neuron were a pure sine wave, as in [40].
Harmonic analysis over $S_{n}$ is subtler than in the classical case, however,
and this was not enough for us to propose a concrete mechanism. After
extensive manual effort and many dead-ends, we realized that a single neuron
had its activations concentrated on the cosets of $F_{20}$, the Frobenius
group of order 20 [14]. All of the activations for permutations in the same
coset had the same value, with very little variance. This was so strange and
unexpected that it warranted further investigation, which ultimately led us to
discover the coset circuit.

For a function $f:G\rightarrow\mathbb{R}$, let $C_{H}(f)$ denote the the
degree to which $f$ concentrates on the cosets $H\leq G$ where:

$C_{H}(f)\coloneqq\frac{\sum_{gH}\operatorname{Var}[f|_{gH}]}{\operatorname{Var}[f]}$

Explicitly $C_{H}(f)$ calculates the degree to which restricting to the cosets
of $H$ reduces the variance of $f$, $C_{H}(f)<1$ implies that $f$ can
meaningfully be understood better by looking at the values that it takes on
cosets. Since $S_{5}$ only has 156 subgroups 111Verified with Sage [50] and
GAP [20]., it is tractable to do an exhaustive search and calculate

$\operatorname{argmin}_{H\in\operatorname{Sub}(G)}C_{H}(f)$

the subgroup that minimizes the variance of $f$ for every neuron in the model.

Figure 6: Ablation:Two cases of ablation. The full lines indicate ablating the
double coset circuits in S5 and S6, the dashed lines indicate ablating the
other neurons that don’t form the double coset circuits.

###  6.2 Ablations

To validate that the coset circuit is not only sufficient but also necessary
to implement multiplication in $S_{n}$, we conduct ablations to observe the
change in accuracy at inference time in two different ways: when the
identified circuit is ablated and when the rest of the network is ablated.

If the identified circuit is necessary to solve the task, then we expect to
see a drop in the accuracy when the identified circuit is removed from the
network. If it is additionally the primary circuit used by the model, we
expect the accuracy to remain high when we ablate the rest of the neurons and
only keep the ones that form the coset circuits.

In figure 6, we observe a similar trend in both cases of ablations in both
$S_{5}$ and $S_{6}$. We selected neurons that concentrate on one irrep above
the threshold of x percent. When we only keep the neurons that have a
concentration higher than 90%, the accuracy remains perfect in $S_{6}$ over 24
runs with various model sizes. The accuracy is near perfect (0.982) in $S_{5}$
over 107 runs. However, when we ablate these neurons, the accuracy drop to
only 0.04 in S6 and 0.08 in $S_{5}$. This aligns with our initial hypothesis
suggesting that the coset circuits are necessary and sufficient.

We also observe that the performance of $S_{5}$ (blue line) has a higher
variance than $S_{6}$ (red line) We hypothesize that this is due to the
smaller model sizes used in $S_{5}$.

###  6.3 Causal Interventions

Intervention | Mean Accuracy | Mean Loss
---|---|---
Base Model | 0.9999 | 1.97e-6
Embedding Swap | 0.01 | 4.76
Switch Left and Right Sign | 1 | 1.97e-6
Switch Left Permutation Sign | 0 | 22.39
Switch Right Permutation Sign | 0 | 22.36
Perturb $\mathcal{N}(0,0.1)$ | 0.9999 | 2.96e-6
Perturb $\mathcal{N}(0,1)$ | 0.978 | 0.0017
Absolute Value Non-Linearity | 1 | 3.69e-13
Perturb $\mathcal{N}(1,1)$ | 0.88 | 0.029
Perturb $\mathcal{N}(-1,1)$ | 0.98 | 0.0021
Table 2: Causal interventions aggregated over 128 runs on $S_{5}$ with
different sizes

To rigorously test the properties of the coset circuit, we carefully designed
_causal interchange interventions_ [21] targeting the properties of different
components in the circuits. We need to confirm that our model of the circuit
serves as a faithful causal abstraction for the behavior of the actual neural
circuit. We aggregated runs over 128 $S_{5}$ models of different and recorded
their average loss and accuracy. Initially, over the initial models without
intervention, we have accuracy extremely close to 1.

#### Embedding Exchange

The left and right embeddings encode different information—membership in right
and left cosets, respectively—and cannot be interchanged. To test this we
intervene to switch the left and right embeddings. After the intervention, we
observed a significant drop in accuracy to 0 and a rise in loss. This aligns
with our expectation that the membership is an important property that can’t
be switched.

#### Switch Permutation Sign

The pre-activations are symmetric about the origin and the sign of the pre-
activations does not matter, only whether or not the pre-activations is equal
to zero. The _relative_ sign of the left and right pre-activations should
matter a lot. To test this, we have three tests: changing the sign of just the
left embeddings, just the right embeddings, and both embeddings. In the case
where we change both the sign and with commutative property, we can still
expect the left and right activation to cancel out. Therefore, we should see a
near-perfect accuracy and near-0 loss. The result is as expected. When we
change the sign of only the left or right embedding, such cancellation law
doesn’t hold anymore. Therefore, we observe a 0 accuracy in both cases.

#### Absolute Value Non-linearity

The circuit can create a perfect 0-1 coset membership switch with multiple
neurons on constructive interference, but every single neuron is noisy and
fundamentally limited by the ReLu non-linearity. To test this, we replace the
ReLU activation function with the absolute value function $x\mapsto|x|$. We
observe perfect accuracy and an even lower loss that a half of the original
loss.

####  ReLU Clip

If the pre-activations are greater than zero and aren’t filtered by the ReLU,
then the magnitude of the activations does not matter, there is no particular
information in or distinction between a small or large pre-activation value.
To test this, we patch the activations of neurons only when they are greater
than some small constant and replace them with a normally distributed value
centered around the mean activation of that neuron.

#### Distribution Change

It is essential to the functioning of each neuron that a large proportion of
the pre-activations are close to zero. To test this we compare how adding
noise from a $\mathcal{N}(-1,1)$ and $\mathcal{N}(1,1)$ affect the performance
of the model. We can see that changing the distribution of the activation in
Perturb $\mathcal{N}(-1,1)$ changes the performance less significantly than
$\mathcal{N}(1,1)$. This indicates that the coset requires 0 as a threshold
value to decide the membership.

The results of these interventions can be viewed in Table 2

##  7 Discussion

###  7.1 Communication and Replication in Mechanistic Interpretability

The project of mechanistic interpretability strives to understand and explain
inner workings of a machine learned model. As the large models that are
popular today are immensely complicated and difficult to deconstruct, a
substantial amount of mechanistic interpretability research is dedicated to
either small models or work that allows insights gleaned from small models to
be extended to larger models.

Unfortunately, our analysis reveals that even allegedly simple cases can be
very challenging to get right. By revising the problem considered by Chughtai
et al. [6] and finding drastically different mechanisms after extensive and
earnest effort, our work reveals how challenging it can be to get the full
picture correct. We refer the reader to Appendix F for a full side-by-side
comparison of our work with Chughtai et al. [6].

Based on our analysis of twelve mechanistic interpretability papers [6, 9, 11,
22, 24, 25, 37, 40, 41, 55, 58, 59] we have identified five core steps in
mechanistic interpretability work:

  1. 1.

Pick a reference data set or distribution that is correlated to the task.

  2. 2.

Identify a subset of nodes in the model’s computation graph that acts as a
neural circuit such that the activations of the circuit are causally connected
to the reference distribution.

  3. 3.

Establish that this circuit accounts for some substantial portion of the
performance on the task.

  4. 4.

Come up with a model of the circuit that faithfully abstracts the its
functionality.

  5. 5.

Causally test that the behavior of your model is faithful across data
distributions.

Many new techniques for accomplishing step 2 such as activation and path
patching [22, 53, 55] have been developed, though in our case we relied on the
spectral properties of permutation groups to tell us where to stark looking.
As [55] discuss, step 3 can also be difficult in larger models.

Steps 4 and 5 are a difficult, manual, and largely ad-hoc process. Once we
have pinpointed the subset of neurons that is doing something important we
still need to interpret what it is doing: what information those neurons are
encoding, the precise mechanism with which those neurons act and are acted
upon by the rest of the network, etc…

We believe that the root issue with [6] is that they could not find a precise
mechanism for matrix-matrix multiplications in a 1-layer network. They got to
step 4 and came up with a compelling theory that fit the evidence and tied in
nicely with prior work such as [3, 40]. Without a concrete and detailed theory
for how the model implements their proposed algorithm their ability to move on
to step 5 and confirm that the network behaves as they predict is limited. Our
work and that of [6] together are a case study in why performing detailed and
circuit-specific tests is necessary. The spectral evidence in the weights and
logits that both of our teams found did not uniquely determine a single
circuit, but was consistent with both the GCR algorithm and the coset circuit.
It was only after performing the causal interchange interventions detailed in
Section 6.3 that we were confident that we understood what the model was
doing.

We believe that one of the most promising paths forward for making step 5 as
easy and rigorous as possible is extending the work of Geiger et al. [21].
There is a long history of interpretability techniques giving inconsistent and
misleading evidence [1, 4, 13, 27], and recent results show that the most
modern techniques can are vulnerable to similar issues [5, 18, 25, 34, 37].
There are ways to mitigate those weaknesses and in our review of the
literature we were encouraged to see that most projects people went to great
lengths to causally test specific features of the circuits that they propose
under a variety of data distributions. Until we have developed better tools to
make performing these tests easier, however, their application will remain ad
hoc.

There is another subtler issue caused by the difficulty of communicating the
precise mechanisms of neural circuits once they have been identified. Lieberum
et al. [32] talk about the dilemma they faced when describing the circuits
they found with pseudocode: they could remain faithful to the matrix algebra
the circuit uses or provide an understandable, high-level explanation, but
struggled to do both. In our work we have opted to keep our explanations as
concrete and close to the actual neurons as possible, but doing so in a way
that people will actually understand has been difficult. Effective
communication of every minor detail and tweak to our architecture, such as
concatenating the embeddings of the left and right permutations, is crucial
for our audience to properly understand the circuit we are trying to explain.
We need to develop better and more specific jargon, a grammar for
communicating the circuits we find in a way that other researchers can
understand. We know that the researchers who are doing the research can be
fooled by explanations, but the situation for people reading and reviewing
interpretability research is even worse. Our experience doing this project and
writing this paper has led us to believe that developing a concise language
for communicating our theories and the circuits we find is essential for
facilitating progress in interpretability.

Finally, even simple examples can give rise to immense complexity. In Zhang et
al. [58] the authors show that which algorithm a network learns can be
sensitive to details of the experimental set-up such as the learning rate and
initialization. While we were able to exactly replicate the results of
Chughtai et al. [6] due to precise reporting, the release of their code, and
personal communication, it is unfortunately common for machine learning
researchers to not fully report their experimental set-up or release all of
their evaluation artifacts. In such settings, it may be impossible to
distinguish between different results due to genuinely different model
behaviors versus ones due to erroneous analysis.

###  7.2 Spectral Information and Grokking

There is now a growing body of work making links between models in highly
constrained domains that exhibit perfect generalization and the domain-
appropriate Fourier transform. Nanda et al. [40] find that models trained on
modular addition encode the dual representation of the cyclic group $C_{p}$
directly and Barak et al. [3] hypothesize that the model is using the spectral
gap calculated via the Fourier transform on the Boolean cube inherent to the
noisy sparse parities problem. We now find that a 1-hidden-layer network uses
Fourier-sparse functions to solve multiplication on permutation groups. There
are known results from complexity and computational learning theory that
functions with low-degree Fourier concentration are, in a precise sense,
“learnable” [42]. Though this still does not provide direct evidence of a
link, we find it intriguing and an exciting direction for future research.

###  7.3 Duality and Interpretable Bases

Though the precise connections between the learning dynamics, the spectral
characteristics of the weights, and the generalization properties of the model
remain opaque, it is absolutely the case that this project would have been
much more difficult (and perhaps impossible) without an interpretable basis
from which to view the weights and activations.

The Fast Fourier Transform (FFT) [10] is widely regarded as one of the most
important algorithms of all time. The generalizations of harmonic analysis to
more complex geometries has also been integral to physics in the last century
[2]. It is not surprising that similar algorithms would prove invaluable in
machine learning and mechanistic interpretability.

There is also a rich representation theory of semigroups and monoids [51] and
existing work describing FFTs for inverse semigroups [35, 36]. It appears
promising that the surprising results of Liu et al. [33] might become
concretely interpretable via the representation theory of the monoids that
they study.

##  8 Conclusion

In this paper we performed an a circuit level analysis to discover the
concrete mechanism a one layer fully connected network uses to solve group
multiplication in $S_{5}$ and $S_{6}$. We showed that the model decomposes
$S_{5}$ and $S_{6}$ into its cosets and uses that structural information to
perfectly implement the task. We related how we found the circuit using the
Group Fourier Transform and our methodology for confirming that our model of
the circuit was faithful to its true behavior. Finally, we surveyed some
modern research in mechanistic interpretability, their methodologies and the
types of evidence they use to confirm their work. The causal interchange
analysis that was crucial for us to confirm our hypotheses is difficult to
perform and, to our knowledge, has not been applied to a real-world problem.
This is an important obstacle for future research to overcome.

## Acknowledgements

We would like to thank Coreweave for donating the computing resources that we
used to run all of our experiments and to Bilal Chughtai for helpful
discussions we had throughout the project. We would also like to thank Nora
Belrose, Aidan Ewart, Hailey Schoelkopf, and Cédric Simal for their helpful
feedback on an earlier draft of this paper.

## References

  * Adebayo et al. [2020] Adebayo, J., Gilmer, J., Muelly, M., Goodfellow, I., Hardt, M., and Kim, B.  Sanity checks for saliency maps, 2020.
  * Atiyah [2007] Atiyah, M. F.  Duality in mathematics and physics, 2007.  URL https://fme.upc.edu/ca/arxius/butlleti-digital/riemann/071218_conferencia_atiyah-d_article.pdf.
  * Barak et al. [2023] Barak, B., Edelman, B. L., Goel, S., Kakade, S., Malach, E., and Zhang, C.  Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit, January 2023.  URL http://arxiv.org/abs/2207.08799.  arXiv:2207.08799 [cs, math, stat].
  * Bolukbasi et al. [2021] Bolukbasi, T., Pearce, A., Yuan, A., Coenen, A., Reif, E., Viégas, F., and Wattenberg, M.  An interpretability illusion for bert, 2021.
  * Casper et al. [2023] Casper, S., Li, Y., Li, J., Bu, T., Zhang, K., Hariharan, K., and Hadfield-Menell, D.  Red teaming deep neural networks with feature synthesis tools, 2023.
  * Chughtai et al. [2023] Chughtai, B., Chan, L., and Nanda, N.  A Toy Model of Universality: Reverse Engineering How Networks Learn Group Operations.  Technical Report arXiv:2302.03025, arXiv, May 2023.  URL http://arxiv.org/abs/2302.03025.  arXiv:2302.03025 [cs, math] type: article.
  * Clausen & Baum [1993] Clausen, M. and Baum, U.  Fast Fourier Transforms for Symmetric Groups: Theory and Implementation.  _Mathematics of Computation_ , 61(204):833–847, 1993.  ISSN 0025-5718.  doi: 10.2307/2153256.  URL https://www.jstor.org/stable/2153256.  Publisher: American Mathematical Society.
  * Cohen & Welling [2016] Cohen, T. and Welling, M.  Group Equivariant Convolutional Networks.  In _Proceedings of The 33rd International Conference on Machine Learning_ , pp. 2990–2999. PMLR, June 2016.  URL https://proceedings.mlr.press/v48/cohenc16.html.  ISSN: 1938-7228.
  * 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, October 2023.  URL http://arxiv.org/abs/2304.14997.  arXiv:2304.14997 [cs].
  * Cooley & Tukey [1965] Cooley, J. W. and Tukey, J. W.  An algorithm for the machine calculation of complex fourier series.  _Mathematics of computation_ , 19(90):297–301, 1965.
  * Davies et al. [2023] Davies, X., Nadeau, M., Prakash, N., Shaham, T. R., and Bau, D.  Discovering variable binding circuitry with desiderata, 2023.
  * Diaconis [1988] Diaconis, P.  _Group Representations in Probability and Statistics_ , volume 11 of _Institute of Mathematical Statistics Lecture Notes_.  Insitute of Mathematical Statistics, Hayward, CA, 1988.  ISBN 0-940600-14-5.
  * Doshi-Velez & Kim [2017] Doshi-Velez, F. and Kim, B.  Towards a rigorous science of interpretable machine learning, 2017.
  * Dummit & Foote [2003] Dummit, D. S. and Foote, R. M.  _Abstract Algebra_.  Wiley, 3rd edition, July 2003.  ISBN 978-0-471-43334-7.
  * Elias M. Stein [2003] Elias M. Stein, R. S.  _Fourier analysis: an introduction_.  Princeton lectures in analysis 1. Princeton University Press, 2003.  ISBN 069111384X,9780691113845.
  * Ellis et al. [2017] Ellis, D., Friedgut, E., and Pilpel, H.  Intersecting Families of Permutations, July 2017.  URL http://arxiv.org/abs/1011.3342.  arXiv:1011.3342 [math].
  * Erdos [1942] Erdos, P.  On an elementary proof of some asymptotic formulas in the theory of partitions.  _Annals of Mathematics_ , 43(3):437–450, 1942.  ISSN 0003486X.  URL http://www.jstor.org/stable/1968802.
  * Friedman et al. [2023] Friedman, D., Lampinen, A., Dixon, L., Chen, D., and Ghandeharioun, A.  Interpretability illusions in the generalization of simplified models, 2023.
  * Fulton & Harris, Joe [1991] Fulton, W. and Harris, Joe.  _Representation Theory_.  Graduate Texts in Mathematics. Springer, New York, NY, October 1991.  ISBN 978-0-387-97495-8.
  * [20] GAP.  Gap – groups, algorithms, and programming, version 4.12.2, 2023.  URL https://www.gap-system.org.
  * Geiger et al. [2023] Geiger, A., Potts, C., and Icard, T.  Causal abstraction for faithful model interpretation, 2023.
  * Goldowsky-Dill et al. [2023] Goldowsky-Dill, N., MacLeod, C., Sato, L., and Arora, A.  Localizing model behavior with path patching, 2023.
  * Gromov [2023] Gromov, A.  Grokking modular arithmetic, January 2023.  URL http://arxiv.org/abs/2301.02679.  arXiv:2301.02679 [cond-mat].
  * Guo et al. [2023] Guo, T., Hu, W., Mei, S., Wang, H., Xiong, C., Savarese, S., and Bai, Y.  How do transformers learn in-context beyond simple functions? a case study on learning with representations, 2023.
  * Hase et al. [2023] Hase, P., Bansal, M., Kim, B., and Ghandeharioun, A.  Does localization inform editing? surprising differences in causality-based localization vs. knowledge editing in language models, 2023.
  * Huang et al. [2009] Huang, J., Guestrin, C., and Guibas, L.  Fourier Theoretic Probabilistic Inference over Permutations.  _Journal of Machine Learning Research_ , 10(37):997–1070, 2009.  ISSN 1533-7928.  URL http://jmlr.org/papers/v10/huang09a.html.
  * Jain & Wallace [2019] Jain, S. and Wallace, B. C.  Attention is not explanation.  In _North American Chapter of the Association for Computational Linguistics_ , 2019.  URL https://api.semanticscholar.org/CorpusID:67855860.
  * Karjol et al. [2023] Karjol, P., Kashyap, R., and Ap, P.  Neural Discovery of Permutation Subgroups.  In _Proceedings of The 26th International Conference on Artificial Intelligence and Statistics_ , pp. 4668–4678. PMLR, April 2023.  URL https://proceedings.mlr.press/v206/karjol23a.html.  ISSN: 2640-3498.
  * Kondor & Trivedi [2018] Kondor, R. and Trivedi, S.  On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups.  In _Proceedings of the 35th International Conference on Machine Learning_ , pp. 2747–2755. PMLR, July 2018.  URL https://proceedings.mlr.press/v80/kondor18a.html.  ISSN: 2640-3498.
  * Kondor, Risi [2008] Kondor, Risi.  _Group theoretical methods in machine learning_.  PhD thesis, Columbia University, New York, NY, 2008.  URL https://dl.acm.org/doi/abs/10.5555/1570977.  Archive Location: world.
  * Kumar et al. [2023] Kumar, T., Bordelon, B., Gershman, S. J., and Pehlevan, C.  Grokking as the Transition from Lazy to Rich Training Dynamics, October 2023.  URL http://arxiv.org/abs/2310.06110.  arXiv:2310.06110 [cond-mat, stat].
  * Lieberum et al. [2023] Lieberum, T., Rahtz, M., Kramár, J., Nanda, N., Irving, G., Shah, R., and Mikulik, V.  Does circuit analysis interpretability scale? evidence from multiple choice capabilities in chinchilla, 2023.
  * Liu et al. [2023] Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C.  Transformers Learn Shortcuts to Automata, May 2023.  URL http://arxiv.org/abs/2210.10749.  arXiv:2210.10749 [cs, stat].
  * Makelov et al. [2023] Makelov, A., Lange, G., and Nanda, N.  Is this the subspace you are looking for? an interpretability illusion for subspace activation patching, 2023.
  * Malandro [2010] Malandro, M. E.  Fast Fourier transforms for finite inverse semigroups.  _Journal of Algebra_ , 324(2):282–312, July 2010.  ISSN 0021-8693.  doi: 10.1016/j.jalgebra.2009.11.031.  URL https://www.sciencedirect.com/science/article/pii/S0021869309006413.
  * Malandro [2015] Malandro, M. E.  Fourier Inversion for Finite Inverse Semigroups.  _SIAM Journal on Discrete Mathematics_ , 29(1):269–296, January 2015.  ISSN 0895-4801.  doi: 10.1137/130932028.  URL https://epubs.siam.org/doi/10.1137/130932028.  Publisher: Society for Industrial and Applied Mathematics.
  * McGrath et al. [2023] McGrath, T., Rahtz, M., Kramar, J., Mikulik, V., and Legg, S.  The hydra effect: Emergent self-repair in language model computations, 2023.
  * Merrill et al. [2023] Merrill, W., Tsilivis, N., and Shukla, A.  A Tale of Two Circuits: Grokking as Competition of Sparse and Dense Subnetworks, March 2023.  URL http://arxiv.org/abs/2303.11873.  arXiv:2303.11873 [cs].
  * Nanda & Bloom [2022] Nanda, N. and Bloom, J.  Transformerlens.  https://github.com/neelnanda-io/TransformerLens, 2022.
  * Nanda et al. [2023a] Nanda, N., Chan, L., Lieberum, T., Smith, J., and Steinhardt, J.  Progress measures for grokking via mechanistic interpretability.  Technical Report arXiv:2301.05217, arXiv, January 2023a.  URL http://arxiv.org/abs/2301.05217.  arXiv:2301.05217 [cs] type: article.
  * Nanda et al. [2023b] Nanda, N., Lee, A., and Wattenberg, M.  Emergent Linear Representations in World Models of Self-Supervised Sequence Models, September 2023b.  URL http://arxiv.org/abs/2309.00941.  arXiv:2309.00941 [cs].
  * O’Donnell [2014] O’Donnell, R.  _Analysis of Boolean Functions_.  Cambridge University Press, 2014.  doi: 10.1017/CBO9781139814782.
  * OEIS Foundation Inc. [2023] OEIS Foundation Inc.  The On-Line Encyclopedia of Integer Sequences, 2023.  Published electronically at http://oeis.org.
  * Olah et al. [2020a] Olah, C., Cammarata, N., Schubert, L., Goh, G., Petrov, M., and Carter, S.  Zoom in: An introduction to circuits.  _Distill_ , 2020a.  doi: 10.23915/distill.00024.001.  https://distill.pub/2020/circuits/zoom-in.
  * Olah et al. [2020b] Olah, C., Cammarata, N., Schubert, L., Goh, G., Petrov, M., and Carter, S.  Zoom In: An Introduction to Circuits.  _Distill_ , 5(3):e00024.001, March 2020b.  ISSN 2476-0757.  doi: 10.23915/distill.00024.001.  URL https://distill.pub/2020/circuits/zoom-in.
  * Plumb et al. [2015] Plumb, G., Pachauri, D., Kondor, R., and Singh, V.  SnFFT: A Julia Toolkit for Fourier Analysis of Functions over Permutations.  _Journal of Machine Learning Research_ , 16(107):3469–3473, 2015.  URL http://jmlr.org/papers/v16/plumb15a.html.
  * Power et al. [2022] Power, A., Burda, Y., Edwards, H., Babuschkin, I., and Misra, V.  Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets, January 2022.  URL http://arxiv.org/abs/2201.02177.  arXiv:2201.02177 [cs].
  * Pyber [1993] Pyber, L.  Enumerating finite groups of given order.  _Annals of Mathematics_ , 137(1):203–220, 1993.  ISSN 0003486X.  URL http://www.jstor.org/stable/2946623.
  * Rubin et al. [2023] Rubin, N., Seroussi, I., and Ringel, Z.  Droplets of Good Representations: Grokking as a First Order Phase Transition in Two Layer Networks, October 2023.  URL http://arxiv.org/abs/2310.03789.  arXiv:2310.03789 [cond-mat, stat].
  * Stein et al. [2023] Stein, W. et al.  _Sage Mathematics Software (Version 10.0.0)_.  The Sage Development Team, 2023.  URL {http://www.sagemath.org}.
  * Steinberg [2016] Steinberg, B.  _Representation Theory of Finite Monoids_.  Universitext. Springer International Publishing, Cham, 2016.  ISBN 978-3-319-43930-3 978-3-319-43932-7.  doi: 10.1007/978-3-319-43932-7.  URL http://link.springer.com/10.1007/978-3-319-43932-7.
  * Varma et al. [2023] Varma, V., Shah, R., Kenton, Z., Kramár, J., and Kumar, R.  Explaining grokking through circuit efficiency, September 2023.  URL http://arxiv.org/abs/2309.02390.  arXiv:2309.02390 [cs].
  * Vig et al. [2020] Vig, J., Gehrmann, S., Belinkov, Y., Qian, S., Nevo, D., Sakenis, S., Huang, J., Singer, Y., and Shieber, S.  Causal mediation analysis for interpreting neural nlp: The case of gender bias, 2020.
  * Vink et al. [2023] Vink, R., Gooijer, S. d., Beedie, A., Gorelli, M. E., Zundert, J. v., Hulselmans, G., Grinstead, C., Santamaria, M., Guo, W., Heres, D., Magarick, J., Marshall, ibENPC, Peters, O., Leitao, J., Wilksch, M., Heerden, M. v., Borchert, O., Jermain, C., Haag, J., Peek, J., Russell, R., Pryer, C., Castellanos, A. G., Goh, J., illumination-k, Brannigan, L., Conradt, M., and Robert.  pola-rs/polars: Python Polars 0.19.0, August 2023.  URL https://doi.org/10.5281/zenodo.8301818.
  * Wang et al. [2022] Wang, K., Variengien, A., Conmy, A., Shlegeris, B., and Steinhardt, J.  Interpretability in the wild: a circuit for indirect object identification in gpt-2 small, 2022.
  * 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.
  * Xu et al. [2023] Xu, Z., Wang, Y., Frei, S., Vardi, G., and Hu, W.  Benign Overfitting and Grokking in ReLU Networks for XOR Cluster Data, October 2023.  URL http://arxiv.org/abs/2310.02541.  arXiv:2310.02541 [cs, stat].
  * Zhang et al. [2023] Zhang, S. D., Tigges, C., Biderman, S., Raginsky, M., and Ringer, T.  Can Transformers Learn to Solve Problems Recursively?, June 2023.  URL http://arxiv.org/abs/2305.14699.  arXiv:2305.14699 [cs].
  * Zhong et al. [2023] Zhong, Z., Liu, Z., Tegmark, M., and Andreas, J.  The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks, June 2023.  URL http://arxiv.org/abs/2306.17844.  arXiv:2306.17844 [cs].

##  Appendix A Author Contributions

#### Dashiell

Wrote the code for training and for calculating the Group Fourier Transform
over $S_{n}$. Performed the initial analyses of models trained on $S_{5}$ and
initially found what we came to call the coset circuit. Designed and ran
causal interchange interventions. Derived formal properties of the coset
circuit. Participated in discussions throughout the project and in writing the
paper.

#### Qinan

Ran training jobs and performed the bulk of circuit analysis on $S_{6}$,
designed and ran ablation experiments and causal interchange interventions,
participated in discussions throughout the project and the writing of the
paper.

#### Honglu

Derived formal properties of the coset circuit, participated in the
discussions throughout the project, and the writing of the paper.

#### Stella

Helped scope the problem and identify and plan the core experiments. Advised
on the interpretation of the analysis and the writing of the paper.

##  Appendix B Experiment Details

We conducted experiments focusing on the permutation group of $S_{5}$ and
$S_{6}$.

Model | Epoch | Linear Layer Size | Embedding Size | Optimizer | Learning Rate
---|---|---|---|---|---
small | 250,000 | 128 | 256 | Adam | 0.001
medium | 250,000 | 1024 | 512 | Adam | 0.001
large | 250,000 | 4096 | 512 | Adam | 0.001
Table 3: $S_{5}$ model information Model | Epoch | Linear Layer Size | Embedding Size | Optimizer | Learning Rate
---|---|---|---|---|---
medium | 200000 | 256 | 512 | Adam | 0.001
medium | 200000 | 1024 | 512 | Adam | 0.001
large | 200000 | 4096 | 512 | Adam | 0.001
Table 4: $S_{6}$ model information

##  Appendix C Extra Graphs

###  C.1 Correlation of the Unembedding Vectors

Figure 7: Correlation of the columns of an unembedding matrix, ordered so that
columns that act on neurons of the same coset circuit type are next to each
other. This illustrates both the amount of redundancy, as very few cosets only
get a single neuron, and the degree to which the unembedding relies solely on
constructive interference. The bulk of the action of the unembedding is just
adding together the neurons from the same coset that have correlation near
one. There are only two sets of neurons that exhibit destructive interference,
which is identified by correlation near $-1$.

###  C.2 $(H_{1},H_{1})$ Circuit

(a) Left Permutation Pre-activations

(b) Right Permutation Pre-activations

(c) Activations of all permutations combinations (pre-ReLU)

(d) Activations of all permutations combinations (post-ReLU)

Figure 8: An example of a coset $(H_{1},H_{1})$ circuit.

###  C.3 Distribution over Subgroups and Cosets

Figure 9: Distribution of coset circuits (as a percentage of neurons in the
linear layer) for 128 runs trained on $S_{5}$.

##  Appendix D Group Theory

In this section, let us recall some basic definitions and propositions in
group theory that are relevant to this paper.

###  D.1 Groups

A group $G$ is a nonempty set equipped with a special element $e\in G$ called
the _identity_ and a multiplication operator $\cdot$ satisfying the following:

  * •

(inverse) For each element $a\in G$, there exists an element $b\in G$ such
that $a\cdot b=b\cdot a=e$.

  * •

(identity) For each element $a\in G$, $a\cdot e=e\cdot a=a$.

  * •

(associativity) For elements $a,b,c\in G$, we have $(a\cdot b)\cdot
c=a\cdot(b\cdot c)$.

The inverse of $a\in G$ is denoted by $a^{-1}$.

######  Example D.1.

The set of integers $\mathbb{Z}$ along with the addition $+$ form a group. The
identity element is $0$. Also with the addition, the same is true for the set
of rational numbers $\mathbb{Q}$, the set of real numbers $\mathbb{R}$ and the
set of complex numbers $\mathbb{C}$.

######  Example D.2.

The symmetric group introduced in Section 3.1 along with the composition of
permutations satisfies the group axioms. The identity element is the identity
permutation leaving each element unchanged.

######  Example D.3.

The set of natural numbers $\mathbb{N}$ and addition _do not_ form a group.
The reason being that the inverse elements do not exist except for $0$.

######  Definition D.4.

Given a group $G$, a subgroup $H$ is a subset of $G$ such that

  * •

$a\cdot b\in H$ for any $a,b\in H$.

  * •

$e\in H$.

  * •

$a^{-1}\in H$.

One can check that $H$ along with the multiplication satisfies the group axiom
as well. $H$ being a subgroup of $G$ is denoted by $H\leq G$.

###  D.2 Cosets and double cosets

######  Definition D.5.

Given a proper subgroup $H<G$ and an element $g\in G$, the set
$gH:=\\{gh~{}|~{}h\in H\\}$ is called a left $H$-coset. Similarly,
$Hg:=\\{hg~{}|~{}h\in H\\}$ is called a right $H$-coset.

$gH$ is sometimes called a coset if the subgroup $H$ is clear from the
context. When we do not mention whether it is a left coset or a right coset,
left coset is the default.

######  Lemma D.6.

Two cosets $g_{1}H$ and $g_{2}H$ are either the same subset of $G$ or disjoint
(i.e., $g_{1}H\bigcap g_{2}H=\emptyset$).

######  Lemma D.7.

If $G$ is a finite group, any two $H$-cosets have the same number of elements.

As a result, one can pick suitable representative elements (but not unique)
$g_{1},\cdots,g_{n}\in G$, so that $g_{1}H,\cdots,g_{n}H$ form a partition of
$G$. Because the cosets have equal sizes, we can also conclude that $|G|$ is
always divisible by $|H|$.

######  Definition D.8.

Given two subgroups $H,L<G$ and an element $g\in G$, the set
$HgL:=\\{hgl~{}|~{}h\in H,l\in L\\}$ is called the $(H,L)$-double coset, or
the double coset if the pair $(H,L)$ is clear from the context.

Double cosets enjoy the similar property as cosets:

######  Lemma D.9.

Two double cosets $Hg_{1}L$ and $Hg_{2}L$ are either the same or disjoint.

As a result, $G$ can be similarly decomposed as a disjoint union of
$(H,L)$-double cosets. However, when $G$ is finite, $(H,L)$-double cosets do
not always come with equal sizes. So the decomposition is not equal-sized.

For simplicity, we call the $(H,H)$-double coset the $H$-double coset.

###  D.3 Normal Subgroups

######  Definition D.10.

A subgroup $N$ is _normal_ in $G$, denoted $N\trianglelefteq G$, if for any
$g\in G$ and any $n\in N$, we have $gng^{-1}\in N$.

A subgroup is normal if and only if the left and right cosets are the same,
i.e., for any $g\in G,\ gN=Ng$. Normal subgroups are important because they
are precisely the groups for which the set of $N$-cosets $G/N$ has a natural
group structure.

######  Definition D.11.

Given a group $G$ and a normal subgroup $N\trianglelefteq G$, the _quotient
group_ $G/N$ is defined to be the set of $N$-cosets endowed with the
multiplication given by $gN\cdot hN=ghN$ for any $g,h\in G$.

The well-definedness of the multiplication is a consequence of $N$ being
normal and its group axioms are straightforward to check.

######  Example D.12.

If $G$ is commutative (for every $g,h\in G$, we have $gh=hg$), every subgroup
$H\leq G$ is normal.

######  Example D.13.

If $G=S_{n}$, the subgroup $S_{n-1}$ fixing the first element is _not_ a
normal subgroup. On the other hand, the alternating subgroup $A_{n}$
(consisting of even permutations) is a normal subgroup of $S_{n}$.

The double cosets of a normal subgroup is simply the usual cosets.

######  Lemma D.14.

Given a normal subgroup $H\trianglelefteq G$, the left $H$-coset and the right
$H$-coset are in one-to-one correspondence. Furthermore, the set of $H$-double
cosets is also in one-to-one correspondence to $H$-cosets.

###### Proof.

By definition, $gHg^{-1}=H$. Therefore, $gH=Hg$. $HgH=gHH=gH$. ∎

###  D.4 Conjugate Subgroups

The cosets of a _normal_ subgroup $N\trianglelefteq G$ themselves form a
group. If $x,\;y\in G$ and $x\in gN$ but $\;y\in hN$, then $xy\in ghN$. If $G$
is not abelian, however, many or even all subgroups are not normal and do not
have this property. For a non-normal subgroup $H$, a $g\notin H$ gives rise to
a different _conjugate_ subgroup $gHg^{-1}$.

In general, the relationship between the cosets of $H$ and $gHg^{-1}$ is
complex, but they will have at least one left and one right coset in common:
$Hg^{-1}=g^{-1}(gHg^{-1})$. Every right coset $Hx$ will have a left coset pair
$y(gHg^{-1})$ such that when multiplied, right coset on the left and left
coset on the right, $Hxy(gHg^{-1})=Hg^{-1}$, specifically when $xy=g^{-1}$.

This relationship between the cosets of pairs of conjugate subgroups is not as
powerful as that of the cosets of normal subgroups, but conjugate subgroups
are guaranteed to exist in non-abelian groups, whereas there are many simple
groups without normal subgroups at all.

This relationship between pairs of conjugate subgroups is also useful enough
that it is used by every model we trained. In general, we have the following:

######  Lemma D.15.

For any $H\leq G$ and an element $g\in G$, the set of conjugate elements
$gHg^{-1}$ forms a subgroup of $G$.

If the conjugate subgroup $gHg^{-1}$ is different than $H$, the left and right
cosets $gH,Hg$ are different.

The double coset circuits operate by first identifying a pair of different
conjugate subgroups $H$ and $gHg^{-1}$. It exploits the fact that the left
coset $gH$ and the right coset $(gHg^{-1})g$ are the same subset of $G$, which
will be fully generalized and elaborated in the later sections.

###  D.5 An important case

When a group $G$ decomposes as only two disjoint $H$-double cosets, any pair
of subgroups conjugate to $H$ shares a left coset with another’s right coset.

######  Lemma D.16.

Let $H_{1},...,H_{n}$ be conjugate subgroups of $G$, such that for each
$H_{i}$ the double coset $H_{i}gH_{i}$ is equal to either $H_{i}$ or
$G\setminus H_{i}$. Then for each pair of subgroups $H_{i}$ and $H_{j}$ there
exists a $g\in G$ such that $H_{i}g=gH_{j}$. Moreover, the only double cosets
of $H_{i}$ and $H_{j}$ are $H_{i}gH_{j}=gH_{j}$ and $H_{i}xH_{j}=G\setminus
gH_{j}$.

###### Proof.

If $i=j$, for any $h\in H_{i}$ the shared coset is the subgroup itself. If
$i\neq j$, because $H_{i}$ and $H_{j}$ are conjugate, there exists a $g\in G$
such that $H_{j}=g^{-1}H_{i}g$. The left coset is equal to the right coset:

$gH_{j}=g(g^{-1}H_{i}g)=H_{i}g$

Notice that the double coset $H_{i}gH_{j}=H_{i}(H_{i}g)=H_{i}g$. But for
$x\neq g$:

$\displaystyle H_{i}xH_{j}$ $\displaystyle=H_{i}xg^{-1}H_{i}g$ (1)
$\displaystyle=(G\setminus H_{i})g$ (2) $\displaystyle=G\setminus H_{i}g$ (3)

∎

###  D.6 Representation Theory

######  Definition D.17.

Given a group $G$, a _representation of $G$_ is a group homomorphism
$\rho_{V}:G\rightarrow GL(V)$ for some finite (but nonzero) dimensional vector
space $V$ over a field $k$. When we do not specifically mention $k$, we use
$\mathbb{C}$ as the default.

In other words, a representation maps a group element $g$ to a linear operator
$f(g):V\rightarrow V$ where $V$ is a vector space of dimension $d$, so that
the group multiplication becomes compositions of linear operators ($f(g\cdot
h)=f(g)\circ f(h)$). Without explicit specifications, all representations in
this paper are assumed to be over complex numbers.

When the context is clear, sometimes we omit the subscript $V$ in the notation
$\rho_{V}$.

The representations of finite groups have a rich and beautiful theory (see
Diaconis [12], Fulton & Harris, Joe [19]). Here, we recall a few basic
definitions and facts without going into details.

######  Definition D.18.

A representation $\rho_{V}:G\rightarrow GL(V)$ is a sub-representation of
$\rho_{W}:G\rightarrow GL(W)$ if $V$ can be identified as a linear subspace of
$W$ so that $\rho_{W}(g)$ restricts to $\rho_{V}(g)$ for all $g\in G$.

######  Example D.19.

For any group $G$, the map $G\rightarrow GL(V)$ sending all elements to the
identity matrix is a representation. When $\text{dim}(V)=1$, we call it the
_trivial representation_ of $G$.

######  Definition D.20.

Given two representations $\rho_{V},\rho_{W}$ of $G$, the direct sum of vector
spaces $V\oplus W$ admits a natural representation of $G$ by letting
$\rho_{V},\rho_{W}$ act on each component separately. We call this the direct
sum of representations $\rho_{V},\rho_{W}$, and denote it by
$\rho_{V}\oplus\rho_{W}$.

######  Definition D.21.

Similarly, given two representations $\rho_{V},\rho_{W}$, the tensor product
$V\otimes W$ admits a natural representation of $G$ by acting on $V,W$
separately and extend by linearity. We call this the tensor product of
representations $\rho_{V},\rho_{W}$, and denote it by
$\rho_{V}\otimes\rho_{W}$.

######  Definition D.22.

A representation $\rho$ of a group $G$ is _irreducible_ , if it does not have
sub-representations other than $\rho$.

We denote the set of all irreducible representations of $G$ by
$\operatorname{Irr}(G)$

######  Lemma D.23.

A representation $\rho$ of a finite group $G$ is a direct sum of irreducible
representations.

######  Example D.24.

The trivial representation of $G$ is irreducible.

######  Example D.25.

The permutation representation maps $S_{n}\rightarrow GL(\mathbb{C}^{3})$,
i.e. $3\\!\times\\!3$ matrices with a single $1$ in each row and column and
zeros everywhere else.

$(2\;1\;3)\mapsto\begin{pmatrix}0&1&0\\\ 1&0&0\\\ 0&0&1\\\
\end{pmatrix}\quad(3\;2\;1)\mapsto\begin{pmatrix}0&0&1\\\ 0&1&0\\\ 1&0&0\\\
\end{pmatrix}$

You can see that the matrices of the permutation representation act on the
basis vectors of $\mathbb{C}^{3}$:

$\begin{pmatrix}0&0&1\\\ 0&1&0\\\ 1&0&0\\\ \end{pmatrix}\begin{pmatrix}x\\\
y\\\ z\end{pmatrix}=\begin{pmatrix}z\\\ y\\\ x\end{pmatrix}$

What it means to be a representation is that the group multiplication becomes
matrix multiplication, so just as $(2\;1\;3)(3\;2\;1)=(2\;3\;1)$,

$\begin{pmatrix}0&1&0\\\ 1&0&0\\\ 0&0&1\\\
\end{pmatrix}\begin{pmatrix}0&0&1\\\ 0&1&0\\\ 1&0&0\\\
\end{pmatrix}=\begin{pmatrix}0&0&1\\\ 1&0&0\\\ 0&1&0\end{pmatrix}$

######  Example D.26.

The permutation representation is _reducible_ , because there is a subspace of
the $\mathbb{C}^{3}$ that is invariant to it’s action.

$\begin{pmatrix}0&0&1\\\ 0&1&0\\\ 1&0&0\\\ \end{pmatrix}\begin{pmatrix}x\\\
x\\\ x\end{pmatrix}=\begin{pmatrix}x\\\ x\\\ x\end{pmatrix}$

Note that there is no permutation matrix acting on the vector
$\begin{pmatrix}x&x&x\end{pmatrix}^{T}$ that will change it, because all of
the components are equal.

As it turns out, there are no _irreducible_ representations of $S_{3}$ that
are three-dimensional. The largest irrep of $S_{3}$ is $\rho_{(2,1)}$, which
is made of $2\\!\times\\!2$.

$\displaystyle(2\;1\;3)$ $\displaystyle\mapsto\begin{pmatrix}-1&0\\\
0&1\end{pmatrix}$ $\displaystyle(3\;2\;1)$
$\displaystyle\mapsto\begin{pmatrix}\frac{1}{2}&-\frac{\sqrt{3}}{2}\\\
\frac{\sqrt{3}}{2}&-\frac{1}{2}\end{pmatrix}$ $\displaystyle(2\;3\;1)$
$\displaystyle\mapsto\begin{pmatrix}-\frac{1}{2}&\frac{\sqrt{3}}{2}\\\
-\frac{\sqrt{3}}{2}&-\frac{1}{2}\end{pmatrix}$

We leave it as an exercise to the reader to verify that
$\rho_{(2,1)}(2\;1\;3)\rho_{(2,1)}(3\;2\;1)=\rho_{(2,1)}(2\;3\;1)$.

Trace is an important notion in linear algebra. Taking trace of a
representation induces an important map from $G$ to $\mathbb{C}$.

######  Definition D.27.

Let $\rho_{V}$ be a representation of $G$. The _character_ of $\rho_{V}$ is a
map $\chi(\rho_{V}):G\rightarrow\mathbb{C}$ given by
$\chi(\rho_{V})(g)=\operatorname{tr}(\rho_{V}(g))$.

######  Lemma D.28.

The character $\chi(\rho_{V})$ takes the same value on a conjugacy class of
$G$. In other words, $\chi(\rho_{V})(h)=\chi(\rho_{V})(ghg^{-1})$.

To distill this property for a wider range of functions, we have the following
definition:

######  Definition D.29.

Let $f:G\rightarrow\mathbb{C}$ be a map. If $f(h)=f(ghg^{-1})$ for any $g,h\in
G$, $f$ is called a _class function_.

For a finite group $G$, the set of class functions form a finite-dimensional
vector space. There is an important inner product between class functions.

######  Definition D.30.

The inner product of two class functions $\phi,\psi$ are defined as:

$\langle\phi,\psi\rangle=\dfrac{1}{|G|}\sum\limits_{g\in
G}\phi(g)\overline{\psi(g)}.$

As we require the class functions to take the same values on conjugacy
classes, the dimension of the vector space of class functions is equal to the
number of conjugacy classes in $G$. On the other hand, we have the following
important theorem:

######  Theorem D.31.

The characters of $\operatorname{Irr}(G)$ forms an orthonormal basis in the
vector space of class functions.

######  Lemma D.32.

For a finite group $G$, $\operatorname{Irr}(G)$ is a finite set. Furthermore,
the order of $\operatorname{Irr}(G)$ is equal to the number of conjugacy
classes in $G$.

##  Appendix E Fourier transform over finite groups

Despite being mostly perceived as a powerful tool in physics and engineering,
the Fourier transform has also been successfully applied in group theory
thanks to its generalization to locally compact abelian groups as well as an
analog over finite groups. The purpose the group Fourier transform serves is
largely analogous to the one served by the classical Fourier transform: it
provides an alternate orthogonal basis with which to analyze functions from a
group $G$ to either $\mathbb{R}$ or $\mathbb{C}$.

To motivate the transition from the classical Fourier theory to the Fourier
theory over groups, we start with a brief recall of the definitions.

The classical Fourier transform over real numbers converts a complex-valued
Lebesgue-integrable function $f:\mathbb{R}\rightarrow\mathbb{C}$ into a
function from the complex unit circle $S^{1}$ to $\mathbb{C}$ with following
formula:

$\hat{f}(\xi)=\displaystyle\int_{-\infty}^{\infty}f(x)e^{-2\pi i\xi x}dx.$ (4)

Taking one step further in abstraction, we note that $e^{-2\pi i\xi x}$ as a
function of $x$ has the defining properties of turning additions into
multiplications (being a group homomorphism) and always having complex norm
$1$:

$\displaystyle e^{-2\pi i\xi(x_{1}+x_{2})}$ $\displaystyle=e^{-2\pi i\xi
x_{1}}\cdot e^{-2\pi i\xi x_{2}},$ $\displaystyle|e^{-2\pi i\xi x}|$
$\displaystyle=1.$

We call such functions the _characters_ of $\mathbb{R}$, though they are often
thought of as _frequencies_. One can prove that all characters of $\mathbb{R}$
can be written as $e^{-2\pi i\xi x}$ for a suitable $\xi\in\mathbb{R}$.

Looking back at (4), the properties we need in order to define the Fourier
transform over $\mathbb{R}$ are:

  * •

$\mathbb{R}$ has the Lebesgue measure (allowing for integration to happen).

  * •

$\mathbb{R}$ is a group (so that the characters make sense as group
homomorphisms from $\mathbb{R}$ to the unit circle group
$S^{1}\subset\mathbb{C}$).

Now, if we are given a finite group $G$, the Fourier transform of a finite
group is an operator converting a map $f:G\rightarrow\mathbb{C}$ into a
function between $\operatorname{Irr}(G)$ and the set of linear operators
$M(V)$.

######  Definition E.1.

Given a group $G$, the _Fourier transform_ of a map $f:G\rightarrow\mathbb{C}$
is a function $\hat{f}$ from $\operatorname{Irr}(G)$ to the union of
$M(\mathbb{C}^{n})$ for all $n$ such that

$\hat{f}(\rho)=\sum\limits_{a\in G}f(a)\rho(a)$

for an irreducible representation $\rho$.

The analogy comes from the following similar facts:

  * •

$G$, as a finite set, has the invariant discrete measure (where the
“integration” becomes the sum).

  * •

$G$ is a group, and the irreps $\rho$ are in a sense the ”smallest” group
homomorphisms from $G$ to $GL(n,\mathbb{C})$ (note that the images of $\rho$
similarly have complex-norm-$1$ determinants due to $G$ being a finite group).

For more details and applications, one can refer to, for example, [15]. We
would like to note that there is also an inverse transform that restores the
original function $f$ from $\hat{f}$:

$f(g)=\frac{1}{|G|}\sum_{\rho\in\operatorname{Irr}(G)}d_{\rho}\operatorname{tr}[\hat{f}(\rho)\rho(g^{-1})]$
(5)

###  E.1 Projection on Fourier Basis

The inputs to the model are two one-hot vectors, $x_{l},\;x_{r}$, which
multiply the embedding matrices $E_{l}x_{l}$ and $E_{r}x_{r}$. $E_{l}$ and
$E_{r}$ are $d\times|G|$ matrices, where $d$ is the embedding dimension and
$|G|$ is the size of the group. The _columns_ are the embedding vectors for a
single element $g\in G$. The normal approach would be to try and look at the
column spaces of $E_{l}$ and $E_{r}$, as these columns are the inputs to the
model. However, since each _row_ of $E_{l}$ and $E_{r}$ and each value of that
row is associated with a single element of $G$, we instead treat each _row_ of
the embedding as a function $f:G\rightarrow\mathbb{R}$.

Figure 10: The evolution of the mean Fourier Entropy per layer over the course
of training for 128 runs trained on $S_{5}$. The maximum value
$\mathbf{H}[\hat{f}]$ can take over $S_{5}$ is $\log(\frac{1}{7})\approx
1.946$. $\mathbf{H}[\hat{f}]=0$ implies that $\hat{f}(\rho)=0$ on all but one
irrep.

In fact, pretty much anywhere in the model where a matrix or set of
activations has $|G|$ in the shape we can expand into the Fourier basis. For
non-abelian groups, each Fourier frequency is an irrep, and the Fourier
transform for each irrep is matrix-valued. This is, on its face, less than
interpretable. Following the techniques outlined in Diaconis [12], however, we
can expand the function at each element $g\in G$ into a new Fourier basis.
Concretely, if our function $f:G\rightarrow\mathbb{R}$ is represented as a
vector, we know from 5 that each element of the vector is a sum of the Fourier
components:

$\begin{bmatrix}f(g_{1})\\\ f(g_{2})\\\ \vdots\\\
f(g_{|G|})\end{bmatrix}=\frac{1}{|G|}\begin{bmatrix}\sum_{\rho}d_{\rho}\operatorname{tr}[\hat{f}(\rho)\rho(g^{-1}_{1})]\\\
\sum_{\rho}d_{\rho}\operatorname{tr}[\hat{f}(\rho)\rho(g^{-1}_{2})]\\\
\vdots\\\
\sum_{\rho}d_{\rho}\operatorname{tr}[\hat{f}(\rho)\rho(g^{-1}_{|G|})]\end{bmatrix}$

We can keep track of all of the Fourier components at once by purposefully not
completing the sum from 5), but instead keep each term into a new dimension:

$\frac{1}{|G|}\begin{bmatrix}d_{\rho_{1}}\operatorname{tr}[\hat{f}(\rho_{1})\rho_{1}(g^{-1}_{1})]&\dots&d_{\rho_{k}}\operatorname{tr}[\hat{f}(\rho_{k})\rho_{k}(g^{-1}_{1})]\\\
d_{\rho_{1}}\operatorname{tr}[\hat{f}(\rho_{1})\rho_{1}(g^{-1}_{2})]&\dots&d_{\rho_{k}}\operatorname{tr}[\hat{f}(\rho_{k})\rho_{k}(g^{-1}_{2})]\\\
\vdots&&\vdots\\\
d_{\rho_{1}}\operatorname{tr}[\hat{f}(\rho_{1})\rho_{1}(g^{-1}_{|G|})]&\dots&d_{\rho_{k}}\operatorname{tr}[\hat{f}(\rho_{k})\rho_{k}(g^{-1}_{|G|})]\\\
\end{bmatrix}$

Though this may seem like it is only making the data more complicated, it
gives us many tools for analyzing the data. In particular, it turns out that
the weights and activations are sparse in this new basis, which gives us a
small path forward in analyzing the mechanisms.

######  Corollary E.2.

If $H_{i}$ and $H_{j}$ are conjugate subgroups of $G$ such that the only two
double cosets are $H_{i}gH_{j}$ and $H_{i}H_{j}$, then each right coset
$H_{i}x$ has a paired left coset $yH_{j}$ where $y=x^{-1}g$ such that for all
$h_{x}\in H_{i}x$ and $h_{y}\in yH_{j}$, $h_{x}h_{y}\in H_{i}gH_{j}$

######  Lemma E.3.

Let $f:G\rightarrow\mathbb{C}$ be constant on the cosets of $H\leq G$ and non-
zero on at least one coset. Then $\hat{f}(\rho)=0$ if the restriction of
$\rho$ to $H$, $\rho|_{H}$ does not contain the trivial representation as a
subrepresentation.

###### Proof.

The function $f$ can be decomposed as the sum of functions

$f_{xH}(\sigma)=\begin{cases}\alpha_{x}\quad\sigma\in xH\\\
0\quad\text{otherwise}\end{cases}$

for each coset $xH$. Because Fourier transform $\hat{f}$ is invariant under
translation we may, without loss of generality, analyze only the function
$f_{H}$. For a given $\alpha_{x}$,
$\hat{f}_{xH}(\rho)=\hat{f}^{x}_{H}(\rho)=\rho(x)\hat{f}_{H}(\rho)$ for all
$x\in G$. Recall the definition of $\hat{f}_{H}(\rho)$ from E.1:

$\displaystyle\hat{f}_{H}(\rho)$ $\displaystyle=\sum_{g\in G}f_{H}(g)\rho(g)$
(6) $\displaystyle=\alpha_{H}\sum_{h\in H}\rho|_{H}(h)$ (7)
$\displaystyle=\alpha_{H}\sum_{h\in
H}T^{-1}[\bigoplus_{\tau_{i}\in\mathcal{T}}\tau_{i}(h)]T$ (8)
$\displaystyle=\alpha_{H}T^{-1}[\bigoplus_{\tau_{i}\in\mathcal{T}}\sum_{h\in
H}\tau_{i}(h)]T$ (9)

where in 8 we decompose $\rho|_{H}$ into a direct sum of irreps of $H$. But
because each $\tau_{i}$ is irreducible, $\sum_{h\in H}\tau_{i}(h)=\mathbf{0}$
unless $\tau_{i}$ is the trivial irrep. Thus, unless the decomposition of
$\rho_{H}$ into irreps of $H$ includes the trivial representation,
$\hat{f}|_{H}=0$ ∎

###  E.2 Logits and Counting Cosets

In Chughtai et al. [6], one way of justifying the GCR algorithm is to study
the correlation between the character functions and the neuron activations. We
would like to argue that the correlation between the GCR and the coset
membership counting function may already exist, and in some simple cases it
can be made explicit.

More precisely, we are measuring the correlation between the character
function $\chi(\rho)$ of an irrep $\rho$ with a set function
$f:G\rightarrow\mathbb{C}$. In this section, we provide an explicit
characterization of $f$ in terms of trace and irreps, when $f$ counts the
membership of cosets.

We are specifically interested in the following situation:

######  Lemma E.4.

Suppose $f:G\rightarrow\mathbb{C}$ is a function such that its Fourier
transform $\hat{f}$ is nonzero only on an irreducible representation $\rho$
and the trivial representation. Let $\hat{f}(\rho)=A\in M(\mathbb{C}^{n})$. We
have the following explicit formula:

$f(\sigma)=\dfrac{d_{\rho}}{|G|}\operatorname{tr}(A\cdot\rho(\sigma^{-1}))+\dfrac{|H|}{|G|}.$
(10)

###### Proof.

This is immediate by the Fourier inversion formula. ∎

In this case, although $f$ is not directly written in terms of
$\operatorname{tr}(\rho(\sigma^{-1}))$, $f$ is correlated with
$\operatorname{tr}(\rho(\sigma^{-1}))$ depending on how much $A$ is
concentrated to the diagonal and how even are the diagonal entries. For the
rest of the section, we show that under certain conditions, Equation (10)
applies verbatim to the functions that count membership of cosets for a
collection of conjugate subgroups.

Given a subgroup $H\leq G$, let $1_{H}$ be the function that takes value $1$
on the subgroup $H$, and takes $0$ otherwise. The action of $G$ on cosets
$G/H$ induces a representation of $G$ on $\mathbb{C}^{|G/H|}$ by permuting the
basis accordingly. We call it the _permutation representation_ of $G$ on
$G/H$.

######  Lemma E.5.

The Fourier transform of $1_{H}$ is nonzero only at the irreducible components
of the permutation representation of $G$ on $G/H$.

###### Proof.

By definition, the Fourier transform of $1_{H}$ on an irrep $\rho$ is

$\widehat{1_{H}}(\rho)=\sum\limits_{a\in H}\rho(a).$

Notice that the image of $\sum\limits_{a\in H}\rho(a)$ are invariant under $H$
due to the symmetry of this expression.

Let $V$ be the vector space where $\rho$ acts on. Under the action of the
subgroup $H$ through $\rho$, one can decompose $V$ as irreps of $H$. We group
them into two parts:

$V=V^{H}\oplus V^{\prime},$

where $V^{H}$ is a direct sum of copies of trivial representation of $H$ (or
in other words, the invariant subspace of $V$ under $H$), and $V^{\prime}$ is
the direct sum of nontrivial irreducible components of $V$.

We immediately see the following by definition:

$\sum\limits_{a\in H}\rho(a)|_{V^{H}}=|H|\cdot\text{Id}_{V^{H}}.$

Also by definition, nontrivial irreps of $H$ do not have invariant subspaces
since they do not admit proper sub-representations. Therefore,

$\sum\limits_{a\in H}\rho(a)|_{V^{\prime}}=0.$

As a result, $\widehat{1_{H}}(\rho)$ is simply a scaled projection to the
invariant subspace of $V$. Whether it is zero depends on whether
$\text{Res}_{H}\rho$ has any trivial components.

By Frobenius reciprocity,

$\langle\text{Ind}^{G}_{H}(1_{H}),\chi(\rho)\rangle=\langle
1_{H},\chi(\text{Res}_{H}(\rho))\rangle_{H},$

where $\chi(\rho)$ is the character of the irrep
$\chi\in\operatorname{Irr}(G)$ given by its traces, and $\langle\cdot\rangle$
is the inner product between class functions.

The left-hand side $\langle\text{Ind}^{G}_{H}(1_{H}),\chi(\rho)\rangle$ is
nonzero if and only if $\rho$ is an irreducible component of the permutation
representation of $G$ on $G/H$. The right-hand side $\langle
1_{H},\chi(\text{Res}_{H}(\rho))\rangle_{H}$ is nonzero if and only if
$\text{dim}(V^{H})\neq 0$

∎

Note that this lemma also works for $1_{gH}$ for a coset $gH$, since Fourier
transforms turns the translation action by $g$ into group multiplication by
$\rho(g)$.

In the double coset circuit, we are specifically interested in the membership
counting functions. More specifically, let $H_{1},\cdots,H_{n}$ be a
collection of conjugate subgroups of $G$. Given an element $\sigma\in G$,
define the membership counting function as

$F(\sigma)=\sum\limits_{i=1}^{n}1_{\sigma H_{i}}.$

Combining all previous results, we have the following corollary describing the
membership counting function $F$.

######  Corollary E.6.

If the permutation representation of $G$ on $G/H_{1}$ has only $2$ irreducible
components, the Fourier transform $\hat{F}$ of the membership counting
function $F$ is nonzero only at these $2$ irreducible components. In
particular, the equation (10) applies to $F$.

One may wonder how restrictive it is for the permutation representation on
$G/H$ to only have $2$ irreducible components. The follow lemma shows that it
applies to our case when $G=S_{n}$ and $H=S_{n-1}$.

######  Lemma E.7.

For $S_{n}$ and the subgroup $S_{n-1}$ fixing one element, the permutation
representation has only two irreducible components.

###### Proof.

The natural representation of $S_{n}$ on $\mathbb{C}^{n}$ (by permuting the
basis) decomposes as a direct sum of trivial representation and the standard
representation of dimension $n-1$. ∎

##  Appendix F The Group Composition via Representations Algorithm

Our work and analysis owes much to ”A Toy Model of Universality,” though we
come to different conclusions. Here we go over in detail the four main threads
of evidence for the GCR algorithm that Chughtai et al. [6] put forward, which
we restate here for clarity: (1) Correlation between the model’s logits and
characters of a learned representation $\rho$. (2) The embedding and
unembedding layers function as a ”lookup table” for the representations of the
input elements $\rho(a),\;\rho(b)$ and the inverse of the target
$\rho(c^{-1})$. (3) The neurons in the linear layer calculate the matrix
product $\rho(a)\rho(b)=\rho(ab)$. (4) Ablations showing that the circuit they
identify is responsible for the majority of the model’s performance. Though we
were able to reproduce and verify almost all of Chughtai et al. [6]’s
experimental results, we did not find evidence for the GCR algorithm. We
instead found evidence that the models were encoding information about coset
membership in their weights and, upon careful analysis, realized that the
connections between functions from $S_{n}\rightarrow\mathbb{R}$ with low
Fourier Entropy and the cosets of $S_{n}$ provides an alternative explanation
for the evidence that Chughtai et al. [6] provide.

###  F.1 Our Interpretation of the Evidence for GCR

Chughtai et al. [6] proposed as a hypothesis the ”Group Composition via
Representations” (GCR) algorithm in which the model encodes the group’s
irreducible matrix representations (irreps) in its weights and performs the
requisite matrix multiplications to solve the task.

Although we replicated almost all of their analytical results, we could not
confirm this hypothesis or find further evidence of the GCR algorithm. Close
analysis revealed alternative explanations for data such as the observed
sparsity in the group Fourier basis and the correlation between the model’s
logits and characters of irreps. We show that all of these observations are
also consistent with the coset circuit we identify.

Ablations Though we do not perform all of the exact ablations that Chughtai et
al. [6] perform, we also find that the weights that show high Fourier
concentration and perform the coset multiplication are integral to the model’s
performance, see Section 6.2.

Irrep Look Up Table We were not able to find any evidence that the embedding
or unembedding layers function as a look-up table for any representation
except for the one-dimensional sign representation. We did find that the
model’s weights and activations _concentrate_ on specific irreps in the group
Fourier basis. This is due, however, to concentration on cosets of specific
subgroups, not because the matrix representations are realized anywhere in the
weights. The relationship between functions that are constant on cosets and
specific irreps is shown in Appendix E.3.

Logit Attribution We also find that the model’s logits correlate with the
character $\chi_{\rho}(abc^{-1})$ when the irrep $\rho$ appears in the Fourier
transform of the model’s weights. This is not, however, because the model has
implemented the matrix product $\rho(ab)\rho(c^{-1})$, but because the model
is counting the number of cosets that $ab$ and $c$ are both in. As we prove in
E.2, if the cosets are of conjugate subgroups that have their Fourier
transform concentrated on the irrep $\rho$ (as we observe for the models in
question), then the number of shared cosets will also correlate with the
characters of $\rho$.

Matrix Multiplication of Irreps We were not able to find any evidence that the
linear layer implements matrix multiplication, again excluding scalar
multiplication of the sign irrep. Instead we show empirically that each neuron
specializes in recognizing a pair of conjugate subgroups that have a set of
shared cosets on which the group multiplication is simpler and predictable.

###  F.2 Evidence GCR Does Not Explain

Concentration on Cosets In the standard basis the pre-activations of the
overwhelming majority of neurons concentrate heavily on the cosets of
subgroups. This is behavior is not predicted by the GCR algorithm.

The Difference Between Subgroups and Irreps We show that more than one
subgroup of $G$ may be have the Fourier transform of its indicator function
concentrate on one irrep, such as $S_{n-1}$ concentrating on entirely on
$(n-1,1)$. Additionally, as we see for subgroups of $S_{6}$, many subgroups do
not concentrate on only one irrep. This makes the assertion that there is a
one-to-one relationship between irreps and circuits difficult to support,
which at the least complicates GCR’s account of the mechanism.

Quantitatively speaking, the irreps (and therefore the GCR) already fail to
catch up with the number of subgroups. Take $S_{n}$ as examples, we have the
following table 222The numbers of subgroups use the A005432 sequence of OEIS
Foundation Inc. [43]. The numbers of irreps use the A000638 sequence of OEIS
Foundation Inc. [43]:

| $S_{5}$ | $S_{6}$ | $S_{7}$ | $S_{8}$ | $S_{9}$ | $S_{10}$ | $S_{11}$ | $S_{12}$ | $S_{13}$
---|---|---|---|---|---|---|---|---|---
Number of subgroups | $30$ | $156$ | $1455$ | $11300$ | $151221$ | $1694723$ | $29594446$ | $404126228$ | $10594925360$
Number of irreps | $11$ | $19$ | $56$ | $96$ | $296$ | $554$ | $1593$ | $3094$ | $10723$

Table 5: The number of subgroups and the number of irreps from $S_{5}$ to
$S_{13}$

.

Asymptotically, the number of subgroups of $S_{n}$ is bounded below as follows
(see [48, Corollary 3.3]):

$2^{(\frac{1}{16}+o(1))n^{2}}\leq|\text{Sub}(S_{n})|,$

whereas the number of irreps of $S_{n}$ is asymptotically the following (see
[17]):

$|\operatorname{Irr}(S_{n})|\sim\dfrac{1}{4n\cdot
3^{\frac{1}{2}}}e^{\pi(\frac{2}{3})^{\frac{1}{2}}n^{\frac{1}{2}}}.$

We see that the former has a much higher asymptotic growth than the latter.

Unembedding Correlations of Neurons We observe that, except in the rare
instances when a ”positive” coset neuron forms, the correlation between
neurons that concentrate on the same coset is $\approx 100\%$. The correlation
between other neurons neurons that concentrate on other cosets but are similar
in Fourier space (have correlated irreps) only have $0-50\%$ correlation.

Coset Circuit Specific Causal Interventions The property that the loss goes
down when we replace the ReLU activation function with absolute value is a
very strange property that GCR does not predict.

##  Appendix G A Walkthrough of an $S_{4}$ Circuit

  1. 1.

In the left embedding layer, encode which right coset of $S^{5}_{4}$ each
permutation is in.

  2. 2.

In the right embedding layer, encode which left coset of $S^{2}_{4}$ each
permutation is in.

  3. 3.

In the left linear layer, query the embeddings for the coset membership of
$\sigma_{l}$. The pre-activations must only be dependent on the membership in
the right cosets of $S^{5}_{4}$. The left pre-activations are $\sigma_{l}\in
S^{5}_{4}\tau_{(i,5)}\mapsto x_{\tau_{i,5}}$.

  4. 4.

In the right linear layer, query the embeddings for the coset membership of
$\sigma_{r}$. The pre-activations must only be dependent on the membership in
the left cosets of $S^{2}_{4}$. The right pre-activations are,
$\sigma_{r}\in\tau_{(2,j)}S_{4}\mapsto x_{\tau_{(}2,j)}$.

  5. 5.

The left and right pre-activations are added together, and again there are
three options.

    1. (a)

If $\sigma_{l}\in S_{4}\tau$ and $\sigma_{r}\in\tau S_{4}$ for the same
transposition $\tau$, then the pre-activation will be 0.

    2. (b)

$\sigma_{l}$ and $\sigma_{r}$ are not in matched cosets and
$x_{\tau_{l}}+x_{\tau_{r}}>0$. Then the neuron fires and the unembedding layer
knows that $\sigma_{l}\sigma_{r}\notin S_{4}$

    3. (c)

$\sigma_{l}$ and $\sigma_{r}$ are not in matched cosets and
$x_{\tau_{l}}+x_{\tau_{r}}<0$. The ReLU will clip the negative pre-activation
to 0.

##  Appendix H Irreducible Representations

###  H.1 Symmetric Group $S_{5}$

For a subgroup $H\leq G$, we can investigate the Fourier transform of the
indicator function $1_{H}$ by looking at its evaluation at each irrep.
Concretely, we first center the indicator function by defining

$f(g)=\begin{cases}-\dfrac{|H|}{|G|},~{}g\not\in H\\\
1-\dfrac{|H|}{|G|},~{}g\in H.\end{cases}$

By doing so, $\hat{f}$ evaluates to $0$ on the trivial representation of $G$.

Given an irrep $\rho\in\operatorname{Irr}(G)$, we first denote the value of
the Fourier transform of $f$ at $\rho$ by $\hat{f}|_{\rho}$. The contribution
of $\rho$ to $\hat{f}$ is defined by the following:

$\dfrac{\|\hat{f}|_{\rho}\|^{2}}{\sum\limits_{\delta\in\operatorname{Irr}(G)}\|\hat{f}|_{\delta}\|^{2}}$

Here, we list all the subgroups of $S_{5}$ and how each irrep of $S_{5}$
contributes to their indicator function. In the first column, we show the
isomorphism type of each subgroup. Different subgroups can have the same
isomorphism type. In the list:

  * •

$C_{n}$ means cyclic groups of order $n$.

  * •

$S_{n}$ means the symmetric group of $n$ elements.

  * •

$A_{n}$ means the alternating group of $n$ elements (the subgroup of $S_{n}$
consisting of even permutations).

  * •

$D_{2n}$ means the $n$-gon dihedral group of order $2n$ (the symmetric group
of regular polyhedron with $n$ edges).

  * •

$F_{20}$ means the Frobenius group of order $20$.

Isomorphism type | Generators | Size | $(4,1)$ | $(3,2)$ | $(3,1^{2})$ | $(2^{2},1)$ | $(2,1^{3})$ | $(1^{5})$
---|---|---|---|---|---|---|---|---
$C_{2}$ | $\langle(12)\rangle$ | 2 | 20.3% | 25.4% | 30.5% | 17% | 6.8% | -
$C_{2}$ | $\langle(12)(34)\rangle$ | 2 | 13.6% | 25.4% | 20.3% | 25.4% | 13.6 | 1.7%
$C_{3}$ | $\langle(123)\rangle$ | 3 | 20.1% | 12.8% | 30.8% | 12.8% | 20.5% | 2.6%
$C_{4}$ | $\langle(1234)\rangle$ | 4 | 13.6% | 25.4% | 20.3% | 25.4% | 13.6% | 1.7%
$C_{2}\times C_{2}$ | $\langle(12),(34)\rangle$ | 4 | 27.6% | 34.5% | 20.7% | 17.2% | - | -
$C_{2}\times C_{2}$ | $\langle(12)(34),(13)(24)\rangle$ | 4 | 13.8% | 34.5% | - | 34.5% | 13.8% | 3.5%
$C_{5}$ | $\langle(12345)\rangle$ | 5 | - | 21.7% | 52.2% | 21.7% | - | 4.4%
$C_{6}$ | $\langle(123),(45)\rangle$ | 6 | 21.1% | 26.3% | 31.6% | - | 21.1% | -
$S_{3}$ | $\langle(123),(12)\rangle$ | 6 | 42.1% | 26.3% | 31.6% | - | - | -
$S_{3}$ 333Referred to as ”twisted” $S_{3}$ in plots. | $\langle(123),(12)(45)\rangle$ | 6 | 21.1% | 26.3% | - | 26.3% | 21.1% | 5.3%
$D_{8}$ | $\langle(1234),(13)\rangle$ | 8 | 28.6% | 35.7% | - | 35.7% | - | -
$D_{10}$ | $\langle(12345),(25)(34)\rangle$ | 10 | - | 45.5% | - | 45.5% | - | 1%
$S_{3}\\!\times\\!S_{2}$ | $\langle(123),(12),(45)\rangle$ | 12 | 55.6% | 44.4% | - | - | - | -
$A_{4}$ | $\langle(12)(34),(123)\rangle$ | 12 | 44.4% | - | - | - | 44.4% | 11.2%
$F_{20}$ | $\langle(12345),(2354)\rangle$ | 20 | - | - | - | 100% | - | -
$S_{4}$ | $\langle(12345),(12)\rangle$ | 24 | 100% | - | - | - | - | -
$A_{5}$ | $\langle(12345),(123)\rangle$ | 60 | - | - | - | - | - | 100%
Table 6: Subgroups of $S_{5}$ and the contribution of each irrep to their
centered indicator function.