# On The Variational Perspectives To The Graph Isomorphism Problem

Turbasu Chatterjee<EMAIL_ADDRESS>Department of Computer
Science and Engineering,
Calcutta Institute of Engineering and Management,
Maulana Abul Kalam Azad University of Technology
Kolkata, India  Shah Ishmam Mohtashim<EMAIL_ADDRESS>Department of
Chemistry,
University of Dhaka,
Dhaka, Bangladesh  Akash Kundu<EMAIL_ADDRESS>Institute of Theoretical and
Applied Informatics,
Polish Academy of Sciences, Bałtycka 5, 44-100 Gliwice, Poland.
Joint Doctoral School, Silesian University of Technology, Akademicka 2a,
44-100 Gliwice, Poland

###### Abstract

This paper studies the Graph Isomorphism Problem from a variational
algorithmic perspective, specifically studying the Quadratic Unconstrained
Binary Optimization (QUBO) formulation of the Graph Isomorphism Problem and
subsequent execution using the Quantum Approximate Optimization Algorithm
(QAOA) and the Variational Quantum Eigensolver (VQE). This study presents the
results of these algorithms and the variations that occur therein for graphs
of four and five nodes. The main findings of this paper include the clustering
in the energy landscape for the QAOA in isomorphic graphs having an equal
number of nodes and edges. This trend found in the QAOA study was further
reinforced by studying the ground state energy reduction using VQEs.
Furthermore, this paper examines the trend under which isomorphic pairs of
graphs vary in the ground state energies, with varying edges and nodes.

##  1 Introduction

Hybrid quantum classical algorithms have emerged as a leading strategy to
obtain quantum advantage in Noisy Intermediate Scale Quantum (NISQ) devices
[27]. One can mention variational quantum algorithms (VQAs) , where the cost
function is evaluated in the quantum circuit whose parameters are optimized by
classical methods. The main advantage of VQAs is that they provide a general
framework for a class of problems [8] [23]. Typically in VQA the goal is to
find a quantum state, which minimizes the energy of a problem Hamiltonian.
Variational Quantum Eigensolver (VQE) [26] , and Quantum Approximate
Optimization Algorithm (QAOA) [11] are among the most remarkable examples of
VQAs.

Meanwhile, quantum annealing (QA) provides us with an alternate way to enable
quantum-enhanced information processing with the same areal application as
VQAs. The key difference between VQAs and QA is that the former is a gate-
based computation, and the latter is quantum-fluctuation-based computation
exploiting quantum mechanical effects such as tunneling and entanglement.
Quantum Annealers are relatively easier to build and have significantly more
qubits than gate-based quantum devices. Physical qubits in Quantum Annealers
are also not equivalent to the ones in gate-based quantum devices [33].

|
---|---

(a)

(b)

Figure 1: The energy values of the QAOA for which the resulting values of
their corresponding quadratic values yield an optimal function value of zero.
(a) Shows the plot of the energy values for which the values of the quadratic
program for the Graph Isomorphism Problem for a four node graph yields a
function value of zero. (b) Shows the plot of the energy values for which the
values of the quadratic program for the Graph Isomorphism Problem for a five
node graph yields a function value of zero. The boxplot shows clearly the
distribution of values, the medians and standard deviations for the absolute
energy values.

The concept of Quantum Annealing is based on the adiabatic theorem in physics,
which involves slowly evolving the ground state of a physical system from the
problem Hamiltonian of the system. Quantum annealing is the underlying
principle for finding the ground state energy of a QUBO Problem. In Quantum
Annealers, the problem Hamiltonian is represented as a Quadratic Unconstrained
Binary Optimization (QUBO) problem [30] [10] [21]. QUBO problems can be easily
converted to Ising formulations according to the needs of the problem.

Studying existing literature, it has been found that different QUBO
formulations for the Graph Isomorphism Problem have been provided by
Lucas[23], Kenneth [34], Calude [7] etc. Kenneth and Calude performed their GI
QUBO formulation experiments on D-Wave’s Quantum Annealer machines. It has
been conjectured that the lowest number of logical qubits required for the
general Graph Isomorphism Problem for two graphs of order n is $n^{2}$. Apart
from GI using QUBO a class of Problems such as Boolean satisfiability [13],
binary clustering [4], classifier training [28], Travelling Salesman Problem
[29] vehicle routing [6], railway dispatching problem [10] is been solved.
Inspired by the results from the works mentioned earlier, this paper’s authors
decided to try out the Graph Isomorphism Problem using QAOA and VQE.

This work presents the first study of the Graph Isomorphism Problem in the
circuit model of quantum computation, according to the best of the authors’
knowledge of scientific literature in the field. The aims of this paper
include:

  1. 1.

Studying the variational formulations for the Graph Isomorphism Problem and
its consequent implementation using the QAOA and the VQE.

  2. 2.

Studying energy landscapes of the QAOA and the VQE.

##  2 Background

|
---|---

(a)

(b)

Figure 2: The illustration of variation in QAOA energies with simultaneous
edge and node reduction. (a) Shows how edges were methodically removed from a
five node complete graph (the graphs are reduced from (j) $\rightarrow$ (a)).
A copy of each graph was used when testing, thereby yielding a pair of
identical graphs, on which the graph isomorphism formulation was carried out.
(b) Shows the QAOA energies of the Hamiltonian for each of these graphs for
which the isomorphic pairs has the quadratic program yield a function value of
zero

For this paper, we try out two existing quantum approach to the Graph
Isomorphism Problem: QAOA and VQE. QUBO formulation was used to get the
problem Hamiltonian for QAOA and VQE. The motivation behind using these
methods for the Graph Isomorphism Problem is described in the following
subsections.

###  2.1 The Graph Isomorphism Problem

The Graph Isomorphism Problem is the computational problem of determining
whether two finite graphs are structurally identical or isomorphic. An
isomorphism of a graph $G=(V,E)$ to a graph $H=(W,F)$ is a one-to-one,
bijective mapping from the vertex set of the first graph $V$ to the vertex set
of the second graph $W$ that preserves adjacency and non-adjacency. It is one
of the very few unsolved Problems in NP. The exact complexity of the problem
has eluded researchers ever since its conception for more than five decades.
The problem is not known to be solvable in polynomial time or NP-complete. It
may be put in the classical complexity class NP-complete. Interestingly, for
many special classes of graphs, the problem can be solved in polynomial time.
If the graphs have different sizes or orders, then they cannot be isomorphic,
and these cases can be decided quickly. The current best known classical
algorithm for the problem has a time complexity of $\exp\left((\log
n)^{O(1)}\right)$ which is quasipolynomial. [2] The quantum computational
complexity of the problem is still unknown. [31] Previous attempts using
quantum algorithms in the light of Hidden Subgroup Problem, using Quantum
Fourier Sampling has been proven to fail. [15] [14] [31]

The Graph Isomorphism Problem has numerous applications in a variety of fields
including the study of chemical compound structure, computational biology,
where a graph representing a molecular compound must be compared to an entire
database, social network security and many more.

####  2.1.1 The Quantum Approximate Optimization Algorithm

QAOA introduced by Farhi et.al [11] finds an approximation to the ground state
of a problem Hamiltonian by constructing a specific variational ansatz through
first order Suzuki-Trotter decomposition approximating adiabatic evolution.
The operators $\textrm{exp}(-i\beta H_{\text{m}})$ and $\textrm{exp}(-i\alpha
H_{\text{o}})$ are applied in alternation resulting in the state

$\lvert\mathbf{\alpha},\mathbf{\beta}\rangle=\prod_{k=1}^{L}\textrm{exp}(-i\beta_{k}H_{\text{m}})\textrm{exp}(-i\alpha_{k}H_{\text{o}})\lvert+\rangle^{\otimes
n},$ (1)

where $H_{\text{o}}$ is the objective and $H_{\text{m}}=-\sum_{j}X_{j}$ is the
mixer Hamiltonian. Under fixed number of layers (i.e. $L$), the algorithm
requires $2L$ parameters. The expectation value
$\langle\alpha,\beta|H|\alpha,\beta\rangle$, of state
$\lvert\alpha,\beta\rangle$ is approximated through measuring the state in the
computational basis. The parameters $\alpha$, $\beta$ are updated using
classical optimization procedure so that the energy is returns optimal value.

On one hand, QAOA can be utilized to solve a class of Problems such as Max-
Cut[12, 24], Max-k-Vertex Cover[9], at the same time, the applicability of
QAOA extends to integer factorization problem[1].

####  2.1.2 The Variational Quantum Eigensolver

The VQE uses Ritz’s variational principle to prepare the ground state and the
corresponding energy. In this algorithm, the quantum computer is used to
prepare variational trial states
$\lvert\psi(\mathbf{\theta})\rangle=U(\mathbf{\theta})|0\rangle$, that depend
on a set of parameters $\theta$. Then, the expectation value of the energy
$\langle\psi(\mathbf{\theta})|H|\psi(\mathbf{\theta})\rangle$, is estimated
and used by a classical optimization procedure to generate a new set of
parameters. The advantage of VQE over classical simulation methods is that we
can efficiently prepare trial states that are not tractable classically. VQE
has a class of applications in physics [25], chemistry, optimization Problems,
and many more.

##  3 Formulation of quadratic program

|
---|---

(a)  (b)

Figure 3: The illustration of the energy for VQE (y-axis) for pairs of graphs
with four nodes in respect with number of iterations (x-axis). The colors
represent different runs on a class of graphs. It can be seen that after $400$
iterations the energies cluster.

The first described baseline penalty Hamiltonian for the graph isomorphism was
introduced in Lucas [23]. Let us consider $G_{1}=(V_{1},E_{1})$, and
$G_{2}=(V_{2},E_{2})$ graphs, where $V$ are the vertices and $E$ edges. The
Hamiltonian is formulated by proposing binary variables $x_{v,i}$, which is
$1$ if the vertex $v$ in $G_{2}$ gets mapped to vertex $i$ in $G_{1}$ as
follows.

$H=A\sum_{v}\left(1-\sum_{i}x_{v,i}\right)^{2}+A\sum_{i}\left(1-\sum_{v}x_{v,i}\right)^{2}+B\sum_{ij\notin
E_{1}}\sum_{uv\in E_{2}}x_{u,i}x_{v,j}+B\sum_{ij\in E_{1}}\sum_{uv\notin
E_{2}}x_{u,i}x_{v,j}.$ (2)

In Zick et.al [31] a modified formulation of Eq.2 is proposed in order to
achieve a simple set of coupler values (e.g. 0, 1 instead of 0, 1, 2 in Lucas)
amenable to quantum annealing. An edge related penalty is applied to a
coupling iff there is not a vertex mapping penalty. The modified Hamiltonian
is given as follows.

$H=A\sum_{v}\left(1-\sum_{i}x_{v,i}\right)^{2}+A\sum_{i}\left(1-\sum_{v}x_{v,i}\right)^{2}+B\sum_{\begin{subarray}{c}ij\notin
E_{1}\\\ i\neq j\end{subarray}}\sum_{uv\in E_{2}}x_{u,i}x_{v,j}+B\sum_{ij\in
E_{1}}\sum_{\begin{subarray}{c}uv\notin E_{2}\\\ u\neq
v\end{subarray}}x_{u,i}x_{v,j}.$ (3)

In Calude [7] a different methods for constructing efficient QUBO formulations
for the Graph Isomorphism Problem. The objective for the formulation is given
as follows.

$F(x)=H(x)+\sum_{ij\in E_{1}}P_{i,j}(x),$ (4)

where

$H(x)=\sum_{0\leq i<n}\left(1-\sum_{0\leq
i^{\prime}<n}x_{i,i^{\prime}}\right)^{2}+\sum_{0\leq
i^{\prime}<n}\left(1-\sum_{0\leq i<n}x_{i,i^{\prime}}\right)^{2},$ (5)

and

$\sum_{ij\in E_{1}}P_{i,j}(x)=\sum_{0\leq
i^{\prime}<n}\left(x_{i,i^{\prime}}\sum_{0\leq
j^{\prime}<n}x_{j,j^{\prime}}\left(1-e_{i^{\prime},j^{\prime}}\right)\right),$
(6)

$e_{i,j}=1$ if $ij\in E_{2}$ and $e_{i,j}=0$ if $ij\notin E_{2}$. This direct
formulation of the quadratic function is done such that a mapping $f$ can be
decoded from that values of the variables in the quadratic program using a
partial function $D$, such that $D:\mathbb{Z}_{2}^{n^{2}}\mapsto\mathcal{F}$,
where $\mathcal{F}$ is the set of all bijections between $V_{1}$ and $V_{2}$.
The domain of $D$ consists of all vectors
$\textbf{x}\in\mathbb{Z}_{2}^{n^{2}}$. Calude et. al. ensures that the
function $H(x)=0$ if and only if $D$ is defined (and bijective). The component
$\sum_{ij\in E_{1}}P_{i,j}(x)=0$ if and only if the mapping $f=D(\textbf{x})$
is edge invariant. Therefore the function $F(\textbf{x})=0$, for all
$\textbf{x}\in\mathbb{Z}_{2}^{n^{2}}$ if and only if $f=D(\textbf{x})$ is an
isomorphism.

##  4 Methodology

The methodology for each experiment is different but was done on a common
dataset unless stated otherwise. The data generator uses the NetworkX library
and generates pairs of isomorphic and non-isomorphic connected graphs. For
graphs having four nodes, the edge count remains in between four and five. On
the other hand, for graphs having five nodes, all the graphs have five edges.
Since the size of the QUBO matrix for a connected pair of graphs having $N$
nodes is $N\times N$, thereby utilizing $N^{2}$ qubits, the problem size was
kept small for the NISQ era hardware simulations and computational
constraints.

The QUBO matrix was generated using GSGMorph [17] from which the quadratic
programs were obtained. For each set of problem instances, the offset value
for all experiments is determined empirically such that the problem yields an
optimal function value of 0 when the graphs are isomorphic, and the optimal
function would raise a positive value when the graphs are non-isomorphic.

###  4.1 Numerical Setup for QAOA

The QAOA was implemented in Qiskit using the QAOA class and utilized the
quadratic program formulated by Calude et al [7]. The quadratic program was
parsed in IBM’s Docplex model, which was used to feed it into the QAOA class.
The QAOA utilized a minimum eigensolver interface that computed a minimum
eigenvalue for the Hamiltonian thus generated by the quadratic program, with
the number of layers in the QAOA being unity.

###  4.2 Numerical Setup for VQE

The Variational Quantum Eigensolver utilizes the VQE class in Qiskit. he
quadratic program was parsed in IBM’s Docplex model, which was used to feed it
into the VQE class. The VQE utilizes the TwoLocal ansatz consisting of RY and
CZ gates with five repetitions and linear entanglement. The SPSA optimizer was
used with a maximum iteration of 600 subjected to MinimumEigenOptimizer class.

##  5 Results and Discussion

###  5.1 QAOA Results

The energies calculated are of the minimum eigenvalues of the converted
problem Hamiltonian from the initial quadratic Docplex model using the
MinimumEigenOptimizer class that takes the quadratic model and converts them
into a tensor product of Pauli matrices. The corresponding minimum energy
eigenvalues of the Hamiltonian for which the quadratic program yields a
minimum eigenvalue of zero are given in Figure 1(a). Similarly, for graphs
with five nodes, the energies are presented in Figure 1(b).

Extending on the results by Szegedy [32], in the light of the Ising
formulation of the Graph Isomorphism Problem, solved using the QAOA, we
observe that the energies for graphs having the same node count have roughly
the same energies, as is evident from the graphs. Moreover, the number of
edges have roughly the same energies, with the energies values being
distributed in a space having a relatively small value of standard deviations.
Furthermore, Szegedy’s result [32] states that for a MAX-CUT formulation of
the QAOA, two isomorphic graphs will yield the same energy values given the
same parameters for the QAOA quantum circuit. These results attempt to
generalize that approach by showing that families of isomorphic graphs have
energies within a very short deviation range. We will attempt to formalize
this argument in the future iterations of this work.

However, in an experiment conducted as part of this study that takes two
identical complete graphs and attempts to methodically remove one edge at
random without replacement, varying the number of edges and the number of
nodes in the graph simultaneously yields the results given in figure 2 (b). It
is observed that as the number of edges and nodes is decreased, the energy
values decrease till edge number 6, but weirdly energy increases from that
point as the number of nodes and edges are reduced.

###  5.2 VQE Results

The results of the QAOA were supported by the results of the VQE, which
yielded an optimal function value of zero for isomorphic graphs and non-zero
for non-isomorphic pairs. It is noted that by using Variational Quantum
Eigensolver, the ground state energies are not only much less(with absolute
energy values being much greater than the QAOA), but the inherent trend of the
energies found by either method is reflected herein. In other words, VQE
results also corroborate the study that families of isomorphic graphs have
energies within a very short deviation range. However, the optimization
results from the VQE are obtained at a much higher time and resource cost.

##  6 Conclusion and Future Work

As a summary, we have tested two different quantum algorithms QAOA and VQE,
for the Graph Isomorphism Problem, where Hamiltonian is established using the
QUBO formulation. We have shown through numerical simulations that the results
of both algorithms support each other in identifying isomorphic and non-
isomorphic pairs for four, and five nodes in a non-noisy device. Thus, we have
proposed a new application area for these two quantum algorithms.

We have shown a few empirical pieces of evidence that agree with previous
literature [32] that QAOA energies of isomorphic graphs cluster together.
Additionally, we have also shown that similar phenomena happen for VQE
simulations as well. As per our knowledge, this phenomenon was not explored in
the case of VQE before this work.

A further investigation of this work can be conducted by expanding the idea of
energies clustering for families of isomorphic graphs and running the
formulation on real devices.

##  7 Acknowledgement

TC and SIM would like to thank Dr. Omar Shehab for the insightful discussions
during the sessions of Banglay Quantum Computing, and, Mr. Amit Saha for his
unrelenting support. AK would like to thank Dr. Özlem Salehi for the fruitful
discussion regarding the QUBO formulation. AK was supported by the National
Science Centre (NCN), Poland, under project number 2019/33/B/ST6/02011.

## References

  * Anschuetz  _et al._ [2018] Anschuetz, Eric R, Jonathan P. Olson, Alán Aspuru-Guzik, and Yudong Cao (2018), “Variational quantum factoring,” arXiv:1808.08927 [quant-ph] .
  * Babai [2016] Babai, László (2016), “Graph isomorphism in quasipolynomial time,” arXiv:1512.03547 [cs.DS] .
  * Barahona [1982] Barahona, F (1982), “On the computational complexity of ising spin glass models,” Journal of Physics A: Mathematical and General 15 (10), 3241–3253.
  * Bauckhage  _et al._ [2017] Bauckhage, Christian, Eduardo Brito, Kostadin Cvejoski, César Ojeda, Rafet Sifa, and Stefan Wrobel (2017), “Ising models for binary clustering via adiabatic quantum computing,” in  _International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition_ (Springer) pp. 3–17.
  * Bonati [2014] Bonati, Claudio (2014), “The peierls argument for higher dimensional ising models,” European Journal of Physics 35 (3), 035002.
  * Borowski  _et al._ [2020] Borowski, Michał, Paweł Gora, Katarzyna Karnas, Mateusz Błajda, Krystian Król, Artur Matyjasek, Damian Burczyk, Miron Szewczyk, and Michał Kutwin (2020), “New hybrid quantum annealing algorithms for solving vehicle routing problem,” in  _International Conference on Computational Science_ (Springer) pp. 546–561.
  * Calude  _et al._ [2017] Calude, Cristian S, Michael J Dinneen, and Richard Hua (2017), “Qubo formulations for the graph isomorphism problem and related problems,” Theoretical Computer Science 701, 54–69.
  * Cerezo  _et al._ [2021] Cerezo, M, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and et al. (2021), “Variational quantum algorithms,” Nature Reviews Physics 3 (9), 625–644.
  * Cook  _et al._ [2020] Cook, Jeremy, Stephan Eidenbenz, and Andreas Bartschi (2020), “The quantum alternating operator ansatz on maximum k-vertex cover,” 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) 10.1109/qce49297.2020.00021.
  * Domino  _et al._ [2021] Domino, Krzysztof, Akash Kundu, Özlem Salehi, and Krzysztof Krawiec (2021), “Quadratic and higher-order unconstrained binary optimization of railway dispatching problem for quantum computing,” arXiv preprint arXiv:2107.03234 .
  * Farhi  _et al._ [2014] Farhi, Edward, Jeffrey Goldstone, and Sam Gutmann (2014), “A quantum approximate optimization algorithm,” arXiv:1411.4028 [quant-ph] .
  * Farhi  _et al._ [2001] Farhi, Edward, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda (2001), “A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem,” Science 292 (5516), 472–475.
  * Farhi  _et al._ [2000] Farhi, Edward, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser (2000), “Quantum computation by adiabatic evolution,” arXiv preprint quant-ph/0001106 .
  * Grigni  _et al._ [2001] Grigni, Michelangelo, Leonard Schulman, Monica Vazirani, and Umesh Vazirani (2001), “Quantum mechanical algorithms for the nonabelian hidden subgroup problem,” in  _Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing_, STOC ’01 (Association for Computing Machinery, New York, NY, USA) p. 68–74.
  * Hallgren  _et al._ [2010] Hallgren, Sean, Cristopher Moore, Martin Rötteler, Alexander Russell, and Pranab Sen (2010), “Limitations of quantum coset states for graph isomorphism,” J. ACM 57 (6), 10.1145/1857914.1857918.
  * Hempel  _et al._ [2018] Hempel, Cornelius, Christine Maier, Jonathan Romero, Jarrod McClean, Thomas Monz, Heng Shen, Petar Jurcevic, Ben P. Lanyon, Peter Love, Ryan Babbush, Alán Aspuru-Guzik, Rainer Blatt, and Christian F. Roos (2018), “Quantum chemistry calculations on a trapped-ion quantum simulator,” Phys. Rev. X 8, 031022.
  * If and Technologies. [2021] If,, and Only If Technologies. (2021), “Gsgmorph,” https://github.com/IffTech/GSG-Morph.
  * Istrail [2000] Istrail, Sorin (2000), “Statistical mechanics, three-dimensionality and np-completeness: I. universality of intracatability for the partition function of the ising model across non-planar surfaces (extended abstract),” in  _Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing_, STOC ’00 (Association for Computing Machinery, New York, NY, USA) p. 87–96.
  * Jozsa [1998] Jozsa, R (1998), “Quantum algorithms and the fourier transform,” Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454 (1969), 323–337.
  * Ladner [1975] Ladner, Richard E (1975), “On the structure of polynomial time reducibility,” J. ACM 22 (1), 155–171.
  * Lewis and Glover [2017] Lewis, Mark, and Fred Glover (2017), “Quadratic unconstrained binary optimization problem preprocessing: Theory and empirical analysis,” arXiv:1705.09844 [cs.AI] .
  * Li  _et al._ [2019] Li, Yifan, Jiaqi Hu, Xiao-Ming Zhang, Zhigang Song, and Man-Hong Yung (2019), “Variational quantum simulation for quantum chemistry,” Advanced Theory and Simulations 2 (4), 1800182.
  * Lucas [2014] Lucas, Andrew (2014), “Ising formulations of many np problems,” Frontiers in Physics 2, 5.
  * Majumdar  _et al._ [2021] Majumdar, Ritajit, Dhiraj Madan, Debasmita Bhoumik, Dhinakaran Vinayagamurthy, Shesha Raghunathan, and Susmita Sur-Kolay (2021), “Optimizing ansatz design in qaoa for max-cut,” arXiv:2106.02812 [quant-ph] .
  * Mohtashim  _et al._ [2021] Mohtashim, Shah Ishmam, Turbasu Chatterjee, Arnav Das, Rishabh Gupta, and Sumit Suresh Kale (2021), “Disordered phase in ising and metastability in cellular potts models hint at glassy dynamics,” arXiv:2106.11298 [quant-ph] .
  * Peruzzo  _et al._ [2014] Peruzzo, Alberto, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien (2014), “A variational eigenvalue solver on a photonic quantum processor,” Nature Communications 5 (1), 10.1038/ncomms5213.
  * Preskill [2018] Preskill, John (2018), “Quantum Computing in the NISQ era and beyond,” Quantum 2, 79.
  * Pudenz and Lidar [2013] Pudenz, Kristen L, and Daniel A Lidar (2013), “Quantum adiabatic machine learning,” Quantum information processing 12 (5), 2027–2070.
  * Salehi  _et al._ [2021] Salehi, Özlem, Adam Glos, and Jarosław Adam Miszczak (2021), “Unconstrained binary models of the travelling salesman problem variants for quantum optimization,” arXiv preprint arXiv:2106.09056 .
  * Santoro and Tosatti [2006] Santoro, Giuseppe E, and Erio Tosatti (2006), “Optimization using quantum mechanics: quantum annealing through adiabatic evolution,” Journal of Physics A: Mathematical and General 39 (36), R393–R431.
  * Shehab and au2 [2017] Shehab, Omar, and Samuel J. Lomonaco Jr au2 (2017), “Quantum fourier sampling is guaranteed to fail to compute automorphism groups of easy graphs,” arXiv:1705.00760 [quant-ph] .
  * Szegedy [2019] Szegedy, Mario (2019), “What do qaoa energies reveal about graphs?” arXiv:1912.12277 [quant-ph] .
  * Venegas-Andraca  _et al._ [2018] Venegas-Andraca, Salvador E, William Cruz-Santos, Catherine McGeoch, and Marco Lanzagorta (2018), “A cross-disciplinary introduction to quantum annealing-based algorithms,” Contemporary Physics 59 (2), 174–197.
  * Zick  _et al._ [2015] Zick, Kenneth M, Omar Shehab, and Matthew French (2015), “Experimental quantum annealing: case study involving the graph isomorphism problem,” Scientific Reports 5 (1), 10.1038/srep11168.


# Dual Process Learning: Controlling Use of In-Context vs. In-Weights
Strategies with Weight Forgetting

Suraj Anand  Michael A. Lepori  Jack Merullo  Ellie Pavlick

###### Abstract

Language models have the ability to perform in-context learning (ICL),
allowing them to flexibly adapt their behavior based on context. This
contrasts with in-weights learning, where information is statically encoded in
model parameters from iterated observations of the data. Despite this apparent
ability to learn in-context, language models are known to struggle when faced
with unseen or rarely seen tokens. Hence, we study structural in-context
learning, which we define as the ability of a model to execute in-context
learning on arbitrary tokens – so called because the model must generalize on
the basis of e.g. sentence structure or task structure, rather than semantic
content encoded in token embeddings. An ideal model would be able to do both:
flexibly deploy in-weights operations (in order to robustly accommodate
ambiguous or unknown contexts using encoded semantic information) and
structural in-context operations (in order to accommodate novel tokens). We
study structural in-context algorithms in a simple part-of-speech setting
using both practical and toy models. We find that active forgetting, a
technique that was recently introduced to help models generalize to new
languages, forces models to adopt structural in-context learning solutions.
Finally, we introduce temporary forgetting, a straightforward extension of
active forgetting that enables one to control how much a model relies on in-
weights vs. in-context solutions. Importantly, temporary forgetting allows us
to induce a dual process strategy where in-context and in-weights solutions
coexist within a single model. 111We release code here for reproducibility

##  1 Introduction

A distinguishing trait of transformers is their ability to perform ‘in-
context’ learning (ICL) (Brown et al., 2020; Dong et al., 2023; Garg et al.,
2023) – the ability to use context at inference time to adjust model behavior,
without weight updates, to generalize to unseen input-output combinations.
This ability enables the models to flexibly accommodate variations in
language. For instance, a model is likely to memorize that the token green is
typically an adjective, but recognize that it is used as a noun in the
sentence The child sat on the main green. If queried to predict the part of
speech (POS) of green, a model using the in-weights strategy would likely
incorrectly predict adjective, while the in-context strategy would allow it to
infer noun.

Recent research has studied the tradeoff between ICL and in-weights learning
(IWL) in transformers (Chan et al., 2022b; Singh et al., 2023; Reddy, 2023;
Chan et al., 2022a). Chan et al. (2022b) found that language-like data
distributional properties play a critical role in the emergence of ICL.
Importantly, they found that ICL and IWL strategies often appear to be in
opposition; only with a particular skew of the label distribution were they
able to promote both strategies to co-occur in a model. With a similar setup,
Singh et al. (2023) found that ICL strategies smoothly decrease in strength
across distributions; furthermore, while they found regularization mitigates
ICL transience, they never arrive at a method that allows ICL and IWL to
permanently co-exist in the same model. An ideal model would encode dual
processes: flexible, context-sensitive operations for out-of-distribution
settings and memorized, static operations for ambiguous contexts or IID
settings (Kahneman, 2011; Miller, 2000).

Figure 1: (Top Left) In our natural setting, we use a part-of-speech probe
trained on BERT representations of sentences from Penn Treebank 3 and evaluate
on templated examples (Section 2). (Top Right) In our synthetic setting, we
train a small masked language model (MLM) on a grammar where the expected
response is conditioned on the part-of-speech of the query (Section 3).
(Bottom Left) An idealization of our main finding: structural ICL is transient
(i.e. decays over training) in both natural and synthetic settings.
Active/temporary forgetting maintains structural ICL in the synthetic setting.
(Bottom Right) T-SNE visualization of token embeddings after standard vanilla
MLM training on synthetic setting (van der Maaten and Hinton, 2008). We see
that embeddings in the head of the distribution clusters together, as do the
unseen token embeddings. The embeddings in the tail of the distribution bridge
between the two clusters. Models using conditional ICL would only generalize
to the heldout examples that exist within the head token distribution. Models
using structural ICL would freely generalize to all token embeddings.

Moreover, prior work (Singh et al., 2023; Chan et al., 2022b) has focused on
what we refer to as conditional in-context learning. That is, they focus on
ICL which generalizes to heldout inputs which are imbued with semantic
information, and thus can be seen as interpolations of seen inputs. Such
conditional ICL algorithms would likely fail to predict that in the sentence
The child sat on the main bluk., the new word bluk is a noun. Conditional ICL
algorithms fail when they include tokens that are undertrained (Land and
Bartolo, 2024; Rumbelow and Watkins, 2023) or newly-introduced (e.g. when
adding languages to an existing model) (Chen et al., 2024). This breakdown in
ICL performance occurs because the model is not encoding a truly content-
independent in-context strategy, and rare and unseen embeddings are often out-
of-distribution after vanilla training, as shown in Figure 1 (Bottom Right).
In contrast, we define structural in-context learning to be the ability of a
model to perform in-context learning on arbitrary tokens, or extrapolations
from seen inputs. We test this by assessing performance on unseen tokens in a
naturalistic and synthetic setting described in Figure 1 (Top Left, Top
Right). While conditional ICL fails on the tail of highly-skewed distributions
Chan et al. (2022b), structural ICL would maintain performance.

We find that structural ICL is also transient. However, while regularization
provides a path to persistence in conditional ICL (Singh et al., 2023), it
does not for structural ICL. Therefore, we propose an extension to active
forgetting – a recent weight resetting technique introduced by Chen et al.
(2024) to help augment models with new tokens – to make structural ICL
persistent. Our modification allows us to coarsely control the strategies that
the model adopts, enabling us to induce a dual process strategy: (structural)
ICL for rare and unseen tokens and IWL for common tokens.

Our main contributions are:

  * •

We define and study the concept of structural ICL in both large models and toy
models using a simple part-of-speech probing task. This allows for true
generalization of in-context strategies for completely unseen tokens. We
discover that MLMs exhibit a (limited) form of structural in-context learning
that emerges early in training, but that this ability quickly vanishes.

  * •

We show active forgetting (Chen et al., 2024) maintains structural ICL in
models. We introduce temporary forgetting, a straightforward extension of
active forgetting that enables one to control how much a model relies on in-
weights vs. in-context solutions.

  * •

We demonstrate that when training with skewed token distributions, temporary
forgetting enables us to induce a dual process strategy where our model uses
an in-weights solution for frequently-seen tokens in the head of the
distribution and a (structural) in-context solution for rare tokens in the
tail.

##  2 (Structural) In-Context Learning is Transient

Recent work has discovered that conditional ICL capabilities slowly degrade in
synthetic settings over the course of training (Singh et al., 2023). Building
on this work, we track the tradeoff of conditional IC vs. IW algorithms in a
naturalistic syntax probing task over the course of training for encoder-only
language models (LMs). More importantly, we also track structural ICL over the
course of training. We study the MultiBERTs, averaging all of our results
across seeds 0, 1, and 2. We calculate error bars in Figure 2 as $\pm 1$
standard error of the mean (SEM).

###  2.1 Task

We design a task that employs templated stimuli to determine the tradeoffs
between different strategies for assigning part of speech to tokens – this
task permits both structural IC and IW solutions. For instance, in the
sentence the dog is happy, there are at least two ways of determining that dog
is a noun: (1) memorize that the token identity “dog” is a noun or (2) extract
that dog is the subject of the sentence from the context. For each layer and
MultiBERT step, we train a binary POS probe on representations of nouns and
adjectives from sentences in the training set of Penn Treebank 3 (PTB-3)
(Marcus et al., 1993). For multi-token words, we average representations
across tokens. See Appendix A.1 for additional details about our probing
setup. We then evaluate the pretrained MultiBERT and probe on a suite of test
sets designed to assess the adoption of in-context or in-weights strategies.
Each dataset contains sentences that obey the template: The <noun> is <adj>
(e.g. The dog is happy). Our evaluation datasets are defined as follows:

  1. 1.

Head: Templated examples where tokens are sampled from the most frequent 1500
nouns and most frequent 1500 adjectives in the training set of PTB-3.

  2. 2.

Tail: Templated examples where tokens are sampled from the least frequent 1500
nouns and most frequent 1500 adjectives in the training set of PTB-3.

  3. 3.

Head Switch: Templated examples where tokens are sampled as in the “Head”
dataset, but where nouns appear in the adjective position and adjectives
appear in the noun position (e.g., The happy is dog).

  4. 4.

Tail Switch: Defined similarly to “Head Switch”, except where the tokens are
sampled from the tail of the token distribution.

  5. 5.

Unseen Token: Templated examples where “nouns” and “adjectives” are sampled
from a set of 1,500 randomly initialized tokens. This metric evaluates
structural ICL performance222We are able to generate novel labels not seen
during train time because the embedding and unembedding matrices are tied in
the MultiBERT models..

Note that the MultiBERTs are trained following Devlin et al. (2019) on a
combination of BookCorpus (Zhu et al., 2015) and English Wikipedia collected
by Turc et al. (2019). As such, the distribution of the training data is
fixed, and our experiments are constrained to the natural distribution of
language. As BookCorpus does not have POS tags readily accessible, we employ
PTB-3 to estimate the noun and adjective distribution of the training data. We
defined nouns and adjectives as words that appeared as each POS, respectively,
over 80% of the time. We chose 1500 examples as this is $\approx 10\%$ of the
number of unique nouns.

Figure 2:  (Left) We exhibit the transience of structural ICL by examining the
Unseen Token Accuracy over time. (Middle) We show the trend of memorization of
tail versus head of distribution over training steps by examining the
difference in Layer 7 Accuracy, where both in-context and in-weights
strategies are possible, and Layer 0 Accuracy, where only an in-weights
strategy is possible; (Right) We display the preference for in-weights
strategy when conflicting with in-context strategy over time.

###  2.2 Training Dynamics

We examine (1) structural in-context learning and (2) the tradeoff between in-
context and in-weight strategies over the course of training.

#### Structural ICL

We find that the MultiBERTs are initially able to perform structural ICL, but
that this capability is transient. In Figure 2 (Left), we present results from
a probe trained on representations from Layer 7 as this layer achieves the
highest probing validation performance on PTB-3. This is consistent with prior
research which demonstrates that syntactic structures are encoded in the
middle layers of MLMs Tenney et al. (2019); Limisiewicz and Mareček (2020).
Furthermore, results across all layers are presented in Appendix A.2.
Structural ICL transience is evident as probe performance on Unseen Tokens
tend to spike early in MultiBERT training before dropping to chance by the end
of training. These results suggest that there is an inductive bias toward
structural ICL that diminishes as information is encoded in the embeddings. As
structural ICL confers the ability to generalize to rare and new tokens, this
raises questions about how we can train models that maintain this ability
throughout training.

#### In-Context vs. In-Weights Strategies

Next, we compare conditional in-context vs. in-weights strategies for observed
tokens. First, we observe that ICL strategies dissipate over training, as more
information is encoded in token embeddings. We approximate the use of in-
context information for determining POS as the difference in performance
between Layer 0 (the embedding layer) and Layer 7. Layer 0 must rely only on
in-weights information as there is no in-context information available; in
contrast, Layer 7 uses contextualization to achieve higher performance (Tenney
et al., 2019; Hewitt et al., 2021). Early in training, this additional in-
context information leads to higher probe accuracy; however, this benefit
disappears over time. Figure 2 (Middle) demonstrates this trend across tokens
at the head and tail of the distribution. Notably, the benefit of in-context
information disappears more quickly for the head of the distribution than the
tail, likely because there are far more gradient updates to head token
embeddings.333We observe that performance gain due to the model’s use of in-
context information decreases across a wide range of syntactic phenomena as
embeddings are enriched during training. We term this the ”Pushdown
Phenomenon” and explore it more thoroughly in Appendix A.4.

As the benefit of the model’s use of in-context information dissipates, we
observe that the model shifts from an in-context to an in-weights strategy in
Figure 2 (Right). Specifically, we find that a model’s preference toward
assigning POS on the basis of token identity (i.e. an in-weights solution)
increases slightly over time when in-context and in-weights information are in
conflict. In other words, models becomes more reliant on in-weights strategies
and less reliant on in-context strategies over the course of training. This
finding aligns with Singh et al. (2023), which analyzed a similar phenomenon
using toy models and a synthetic task. Additionally, we observe that the
degree to which the model adopts an in-weights strategy varies significantly
for tokens selected from the head versus the tail of the distribution. When
assigning POS to tokens in the the head of the distribution, the model relies
almost exclusively on an in-weights solution, while the model relies on both
in-weights and in-context solutions when assigning POS to tokens in the tail.

In summary, we find that (1) the benefit of the model’s use of context
information disappears over time and (2) reliance on in-weights information
increases over time, varying depending on the distributional properties of the
token that we are probing.

##  3 Synthetic Task: Distributional Parameters Impact In-Context Learning

We develop a synthetic masked language modeling task to reproduce the above
trends, in order to characterize how distributional parameters affect the
learning strategy that the model adopts. Our synthetic task requires the model
to determine which of two classes a word belongs to. This may be derived
either from in-context information or by memorizing token identity-class
associations in the embedding layer. We draw analogies between these classes
and POS in natural language.

Our vocabulary contains tokens that represent nouns, adjectives, and a copula
(i.e. is). Each sentence is created by selecting (1) a sequence $S$, (2) a
query $Q$, and (3) a response pattern $P$. Our MLM is trained to predict
$\mathbb{P}(P_{i}|S,Q)$ for all $i\in\\{0,\ldots,|P|-1\\}$ (i.e. the
probability of each pattern token). The sequence and pattern are arbitrary and
designed so that no exceedingly simple heuristic may solve this task.

  * •

sequence $S$: Either <noun> <copula> <adj> or  <copula> <adj> <noun>.

  * •

query $Q$: Either the <noun> or <adj> from the sequence.

  * •

pattern $P$: Either <adj> <noun> <noun> if the query is a <noun> or <adj>
<adj> <adj> if the query is an <adj>.

This task is designed such that the model must make a POS classification on
the query token, and then perform some additional operation conditioned on
that classification (copying specific token identities in a specific order).
See Appendix A.5 for more details. See Figure 1 for an example.

We parameterize the task with vocabulary size $v$, the sampling distribution
skew for nouns/adjectives $\alpha$ (where we select $\texttt{<noun>,
<ad>}\sim\text{Zipf}(\alpha)$), and the ambiguity of token POS $\varepsilon$.
The ambiguity parameter determines the percentage of tokens can act as both as
noun and an adjective, and is inspired by the inherent ambiguity of POS in
natural language. For our primary experiments, we fix $\varepsilon=0.10$.
Note, we find that $\varepsilon$ must be greater than zero for an in-context
solution to emerge at all. We compare our skewed distribution results to
sampling tokens from a Uniform distribution.

In this task, an ICL solution to derive the POS of the query may achieve
perfect accuracy by utilizing in-context information (e.g. a copula is always
followed first by an adjective, then a noun). In contrast, an IWL solution to
derive the POS of the query may achieve at most an accuracy of
$(1-\varepsilon/2)$ due to ambiguous tokens. To account for this, we evaluate
our models only on tokens that are not ambiguous; thus, both an ICL and IWL
solution could achieve perfect accuracy. (Ambiguous tokens always use an ICL
solution.)

Our task is formatted in a cloze-style where each token in the pattern is
masked. We employ a MLM (Devlin et al., 2019) to predict the identities of
these masked tokens, with hyperparameters described in Appendix A.6. Near-
perfect validation accuracy is achieved after <60,000 steps on all
experimental settings.

In addition to performance on a randomly selected validation set, we create
datasets to evaluate the model’s preferred strategy throughout training,
similar to Section 2. All examples in these datasets contain novel <adj>,
<noun> pairs. Much like our naturalistic setting metrics in Section 2.1, we
create Tail, Head, Head Switch, Tail Switch, and Unseen Token Accuracy
metrics. In this setting, our head and tail metrics use the top and bottom 10%
of the token distribution by count, respectively.

Figure 3: (Top) In-context performance by distribution with vanilla training;
(Bottom) In-context performance by distribution with active forgetting. The
parameters used are $v=10000,\varepsilon=0.10$. Note that the Uniform
distribution does not have a head or a tail, so its results are in the head
graphs.

###  3.1 Training Dynamics

#### Structural ICL

We largely reproduce the results from the natural language setting presented
in Section 2: structural in-context solutions emerge quickly, but are
transient. This is shown by the early peak of Unseen Token Accuracy, followed
by its steep drop. This trend holds across all tested distributions in Figure
3 (Top Left). As such, both the syntactic and naturalistic settings align with
our idealized graph of structural ICL transience exhibited in Figure 1 (Bottom
Left). However, the disappearance of a structural in-context algorithm occurs
extremely quickly compared to our MultiBERT experiments, likely due to the
simplicity of our synthetic task.

#### In-Context vs. In-Weights Strategies

In this section, we analyze whether models adopt conditional ICL or IWL
strategies over the course of training. Our results are presented in Figure 3.
Importantly, we find that increasing the skew of a distribution increases the
pressure toward an IWL strategy. Conversely, examples with tokens drawn from a
Uniform sampling distribution show a comparatively higher ICL preference (and
thus lower IWL preference) than any Zipfian sampling distribution in Figure 3
(Top Middle). Among Zipfian skewed distributions, the model’s strategy varies
based on whether the adjective and noun are in the head or the tail of the
token distribution, much like in our naturalistic task. As in Section 2, we
find that all skewed distributions prefer a IWL strategy for head tokens.
However, for tail tokens, distributions of moderate skew
($\alpha=1.0001,\alpha=1.2$) prefer an ICL strategy as shown in Figure 3,
while highly skewed distributions ($\alpha=1.5$) fail altogether as shown in
Appendix A.7. This is likely due to the fact that these tokens are rarely
observed in the training data. This illustrates an important distinction
between structural ICL and conditional ICL – a structural ICL solution would
maintain performance on the tail of highly skewed distributions. Additional
experiments exploring the effect of ambiguity are located in Appendix A.8 and
the effect of vocabulary size are located in Appendix A.9.

##  4 Maintaining Structural ICL with Active Forgetting

In Sections 2 and 3, we have demonstrated that as information gets memorized
in the embeddings, the benefits of in-context information dissipate and models
shift to an IWL strategy. In an effort to promote structural ICL, we utilize a
recently-introduced training procedure: active forgetting (Chen et al., 2024).
When training a model using active forgetting, we re-initialize the embedding
matrix every $k$ steps during training. The intuition behind this is that the
model must employ in-context strategies to achieve high accuracy, as no
information can be preserved in each token’s embedding. In other words, the
model can no longer assume that the input embeddings encode any particular
information and thus must develop a structural ICL strategy. While after
vanilla training, these unseen embeddings are out-of-distribution as
illustrated in Figure 1 (Bottom Right), we hypothesize that these unseen
embeddings would align with seen embeddings after training with active
forgetting. We explore this hypothesis in Section 6.

Training our models with active forgetting successfully engenders structural
ICL, enabling the model to approach perfect performance on the Unseen Token
Set (See Figure 3, Bottom Left). Given two random embeddings representing a
noun and an adjective, the model can now (1) derive the POS of these tokens
and (2) output the identity of these out-of-distribution embeddings in the
desired pattern. Note that we see a slightly more stochastic version of our
idealized trend from Figure 1 (Bottom Left) due to the resetting mechanism.

We test $k=100,1000,5000$ and settle on $k=1000$, as this worked well in our
preliminary exploration. With active forgetting, both the head and the tail of
the training distribution prefer an asymptotic in-context strategy across all
tested skews (See Figure 3, Bottom). Still, as the skew of the distribution of
nouns and adjectives increases, there is greater pressure to memorize the head
of the distribution (as these tokens are observed more frequently). Thus, it
takes longer for the model to exhibit a preference towards in-context
solutions for head tokens (e.g. almost 60,000 steps for the $\alpha=1.5$
setting) and there is a much larger drop-off in performance after every
instance of forgetting the embedding matrix.

##  5 Dual Process Learning with Temporary Forgetting

Figure 4: In-weights preference is coarsely controllable by varying temporary
forgetting parameter $N$. All $N>0$ settings in figure induce success on
completely abstracted generalization for all $N$. Note $N=0$ is vanilla
training and $N=\infty$ is active forgetting. Parameters used are
$v=10000,\varepsilon=0.10,\alpha=1.5$.

While active learning successfully induces a structural ICL strategy, our
model loses the ability to memorize information in its embeddings. This is
detrimental in a variety of cases, such as when in-context information is
insufficient to generate an appropriate response. An optimal model would
encode a dual process strategy: maintaining a structural ICL solution while
also memorizing useful linguistic properties (Chan et al., 2022b). We modify
the paradigm of active forgetting to attempt to induce a bias for structural
in-context strategies in the tail of the distribution while preserving the in-
weights solutions for frequently-observed tokens. We introduce temporary
forgetting, where we perform active forgetting every $k$ steps for the first
$N$ steps ($N>>k$) of training. After this point, we allow the embedding
matrix to train as normal.

We find that by varying $N$, we can vary the model’s dependence on in-weights
information on frequently seen tokens while maintaining structural ICL
performance as displayed in Figure 4. If $N$ is too large, this training
procedure mimics the behavior of active forgetting, eliminating in-weights
solutions in favor of structural in-context solutions. Additionally, if $N$ is
too small, the training only sometimes maintains structural ICL performance;
note, however, that this seems to be an all-or-nothing effect. The sweet spot
for $N$ depends on the skew of the distribution. We show that in the
$\alpha=1.5$ case, we can specifically control the preference for an in-
weights strategy over an in-context strategy on observed tokens by modifying
$N$ (See Figure 4). In general, by manipulating the $k$ we reset the
embeddings and $N$, we can calibrate the relative strength of in-context vs.
in-weights strategies.

Thus, temporary forgetting enables a model to successfully encode two distinct
strategies for the same task. While this dual process strategy was previously
demonstrated in Zipfian distributions with $\alpha\approx 1.0$, we can now
induce this behavior for any distribution $\alpha\geq 1.0$, while also
inducing structural ICL behavior on all distributions (See Figure
5).444Distributions where $\alpha\leq 1.0$ would likely only rely on an in-
context strategy Note that the control granted by temporary forgetting over
head IWL preference has limits – we can push up to almost 90% the original IWL
preference while maintaining a high tail ICL preference.

Temporary forgetting imparts an incentive that significantly enhances our
ability to balance between in-context and in-weights strategies, overcoming
inherent biases in naturally occurring data. By tuning the hyperparameters
($k,N$), one can bias the model toward either type of solution.

Figure 5: (Left) Temporary forgetting achieves near perfect unseen token
performance (structural in-context) asymptotically among distributions.
(Right) In addition, temporary forgetting can asymptotically hold preference
for an in-weights strategy in the head of the distribution while holding
preference for an in-context strategy in the tail of the distribution (i.e.
learn dual processes). Parameters used are $v=10000,\varepsilon=0.10$ and
optimal hyperpameters $k,N$ over gridsearch.

##  6 Embedding Analysis

We perform qualitative analyses on the embeddings produced by vanilla
training, active forgetting, and temporary forgetting in order to better
understand how these training regimens impact model representations. These
analyses, consisting of principal component analysis (PCA) and probing for
POS, are located in Appendix A.10.

After vanilla training, the learned embeddings cluster according to their POS,
far from the distribution of randomly-initialized tokens. We train a linear
probe on these learned embeddings, and find that it can almost perfectly
partition nouns and adjectives. Note that the disappearance of structural ICL
occurs at the same time as the probe achieves above-random POS probing (i.e.
memorization).

As expected, we do not see any structure in the embeddings produced after
active forgetting. As such, a linear POS probe trained on these embeddings
never achieves above random chance throughout training. The embedding
distribution looks quite similar to the random initialization distribution,
indicating that no information has been encoded in these embeddings.

Finally, the temporary forgetting setting reflects aspects of both vanilla
training and active forgetting; that is, the head of the token distribution
learns to partition nouns and adjectives whereas the tail of the distribution
does not learn any structure. The tail embeddings much more closely resemble
the initialization distribution with temporary forgetting than with vanilla
training. This results in a unseen token generalization in addition to
memorized information.

##  7 Related Work

#### In Context v. In Weights

A body of recent literature closely examines in-weights versus in-context
learning (Chan et al., 2022b, a; Reddy, 2023; Raparthy et al., 2023; Fu et
al., 2024). The emergence of in-context learning abilities in transformers has
been shown to depend on the distributional properties of the training data
such as burstiness, training class rarity, and dynamic meaning (Chan et al.,
2022b; Reddy, 2023). While we employ a similar analytical framework to this
work, we (1) consider truly random heldout inputs and novel outputs/labels,
(2) evaluate on large, natural language models, and (3) consider structural
ICL. Additionally, while transience of in-context solutions has been noted in
Singh et al. (2023), we find transience of structural ICL, and find that the
adoption of conditional ICL actually increases over training for our synthetic
setting. Additionally, unlike Singh et al. (2023), we find that increasing
L2-regularization does not affect the transience of structural ICL in our
synthetic setting (See Appendix A.7). Finally, we introduce temporary
forgetting to solve what both Singh et al. (2023) and Chan et al. (2022b)
suggest to be an extremely useful behavior: the co-existence of in-context
learning and in-weights learning.

More broadly, the conflict between context-dependent and context-independent
(or reflexive) solutions has been well-studied in the cognitive and
computational neuroscience literature (Russin et al., 2024; Rougier et al.,
2005; Russin et al., 2022). A key feature of human intelligence, termed
cognitive control, is the ability to maintain dual strategies and flexibly
deploy either one in response to particular stimulus. Any artificial system
that aspires to producing human-like behavior must therefore be capable of
maintaining both of these solutions.

#### Weight Forgetting To Help Learn.

While most literature on forgetting characterizes this phenomenon as
undesirable (Kemker et al., 2017; Kirkpatrick et al., 2017; McCloskey and
Cohen, 1989; Ratcliff, 1990), recent neuroscience literature has shown that
intentional forgetting may have positive roles in certain contexts (Srivastava
et al., 2014; Pastötter et al., 2008; Levy et al., 2007; Anderson and Hulbert,
2021). Intentional forgetting in neural networks is accomplished by resetting
a subset of parameters during training. On computer vision tasks, this
resetting procedure has been shown to help low compute and data resource
generalization (Alabdulmohsin et al., 2021; Taha et al., 2021; Ramkumar et
al., 2023). Additionally, Zhou et al. (2022) show that a forget-and-relearn
paradigm helps language emergence. Our method of forgetting embeddings is
directly inspired by Chen et al. (2024), which shows forgetting during
pretraining boosts linguistic plasticity for multilingual learning. As far as
we know, we are the first to propose using forgetting to induce ICL.

##  8 Discussion

This research provides insights into the interplay between structural ICL,
conditional ICL and IWL within transformers. We shed light on several critical
factors determining how models manage and utilize the encoded and contextual
information when faced with novel tokens and tasks.

#### Structural In-Context Learning

One of our key findings is the transience of structural ICL in LMs. Initially,
models exhibit a strong ability to leverage structural ICL, generalizing
algorithms to unseen tokens. However, this capability dissapears as training
progresses, suggesting an initial inductive bias towards structural ICL that
wanes as the model learns. This transience limits generalization on rare
tokens and new tokens. We find that active forgetting maintains structural ICL
by repeatedly reinitializating the embeddings. Our temporary forgetting
training procedure enables a dual process strategy through strategic re-
initialization of weights. This enables adaptability while still leveraging
accumulated knowledge.

#### Implications for Model Training and Application

Our findings are useful to design training protocols that result in flexible
models. A significant reason for the success of LMs is their capacity for ICL
and IWL strategies to co-exist, a behavior that organically occurs with a
moderately skewed Zipfian distribution. However, most natural domains such as
protein discovery, network traffic, and video recording face even more skew,
breaking down this ideal behavior. Our temporary forgetting technique
facilitates a dual process strategy regardless of skew, which could
potentially bring some of the profound success of LMs to other domains.

#### Future Directions and Limitations

The research opens up several avenues for future investigation. Future
research should examine Structural ICL across different model architectures
and configurations. One significant limitation is that our temporary
forgetting experiments were not performed on LMs. Our compute resources
limited such experiments, but we believe this is a critical future step to
refining this training intervention. Another limitation of our work is that
the optimal hyperparameters to temporary forgetting are not known a priori,
and might require several runs to tune. Finally, another avenue of fruitful
future research may be the translation of structural ICL algorithms into
symbolic systems. As structural ICL does not rely on the content of the input,
it should be possible to use techniques like circuit analysis (Räuker et al.,
2023) to reverse-engineer an explicit symbolic representation of the algorithm
that the neural network uses to solve a task.

#### Conclusion

This study deepens our understanding of a model’s adoption of structural ICL,
conditional ICL, and IWL strategy during training. The techniques introduced
here not only enhance our theoretical understanding but also offer practical
tools for improving model training and functionality in real-world
applications.

## References

  * Alabdulmohsin et al. (2021) Ibrahim Alabdulmohsin, Hartmut Maennel, and Daniel Keysers.  The impact of reinitialization on generalization in convolutional neural networks, 2021.
  * Anderson and Hulbert (2021) Michael C Anderson and Justin C Hulbert.  Active forgetting: Adaptation of memory by prefrontal control.  _Annual Review of Psychology_ , 72(1):1–36, 2021.  doi: 10.1146/annurev-psych-072720-094140.  URL https://doi.org/10.1146/annurev-psych-072720-094140.
  * Belrose et al. (2024) Nora Belrose, Quintin Pope, Lucia Quirke, Alex Mallen, and Xiaoli Fern.  Neural networks learn statistics of increasing complexity, 2024.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  _CoRR_ , abs/2005.14165, 2020.  URL https://arxiv.org/abs/2005.14165.
  * Chan et al. (2022a) Stephanie C. Y. Chan, Ishita Dasgupta, Junkyung Kim, Dharshan Kumaran, Andrew K. Lampinen, and Felix Hill.  Transformers generalize differently from information stored in context vs in weights, 2022a.
  * Chan et al. (2022b) Stephanie C. Y. Chan, Adam Santoro, Andrew K. Lampinen, Jane X. Wang, Aaditya Singh, Pierre H. Richemond, Jay McClelland, and Felix Hill.  Data distributional properties drive emergent in-context learning in transformers, 2022b.
  * Chen et al. (2024) Yihong Chen, Kelly Marchisio, Roberta Raileanu, David Ifeoluwa Adelani, Pontus Stenetorp, Sebastian Riedel, and Mikel Artetxe.  Improving language plasticity via pretraining with active forgetting, 2024.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding, 2019.
  * Dong et al. (2023) Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Zhiyong Wu, Baobao Chang, Xu Sun, Jingjing Xu, Lei Li, and Zhifang Sui.  A survey on in-context learning, 2023.
  * Elazar et al. (2020) Yanai Elazar, Shauli Ravfogel, Alon Jacovi, and Yoav Goldberg.  When bert forgets how to POS: amnesic probing of linguistic properties and MLM predictions.  _CoRR_ , abs/2006.00995, 2020.  URL https://arxiv.org/abs/2006.00995.
  * Fu et al. (2024) Jingwen Fu, Tao Yang, Yuwang Wang, Yan Lu, and Nanning Zheng.  How does representation impact in-context learning: An exploration on a synthetic task, 2024.  URL https://openreview.net/forum?id=JopVmAPyx6.
  * Garg et al. (2023) Shivam Garg, Dimitris Tsipras, Percy Liang, and Gregory Valiant.  What can transformers learn in-context? a case study of simple function classes, 2023.
  * Hewitt and Manning (2019) John Hewitt and Christopher D. Manning.  A structural probe for finding syntax in word representations.  In Jill Burstein, Christy Doran, and Thamar Solorio, editors, _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4129–4138, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1419.  URL https://aclanthology.org/N19-1419.
  * Hewitt et al. (2021) John Hewitt, Kawin Ethayarajh, Percy Liang, and Christopher Manning.  Conditional probing: measuring usable information beyond a baseline.  In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih, editors, _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 1626–1639, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.emnlp-main.122.  URL https://aclanthology.org/2021.emnlp-main.122.
  * Kahneman (2011) Daniel Kahneman.  _Thinking, fast and slow_.  macmillan, 2011.
  * Kemker et al. (2017) Ronald Kemker, Angelina Abitino, Marc McClure, and Christopher Kanan.  Measuring catastrophic forgetting in neural networks.  _ArXiv_ , abs/1708.02072, 2017.  URL https://api.semanticscholar.org/CorpusID:22910766.
  * Kirkpatrick et al. (2017) James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A. Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, Demis Hassabis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell.  Overcoming catastrophic forgetting in neural networks.  _Proceedings of the National Academy of Sciences_ , 114(13):3521–3526, March 2017.  ISSN 1091-6490.  doi: 10.1073/pnas.1611835114.  URL http://dx.doi.org/10.1073/pnas.1611835114.
  * Land and Bartolo (2024) Sander Land and Max Bartolo.  Fishing for magikarp: Automatically detecting under-trained tokens in large language models, 2024.
  * Levy et al. (2007) Benjamin J. Levy, Nathan D. McVeigh, Alejandra Marful, and Michael C. Anderson.  Inhibiting your native language: The role of retrieval-induced forgetting during second-language acquisition.  _Psychological Science_ , 18(1):29–34, 2007.  ISSN 09567976, 14679280.  URL http://www.jstor.org/stable/40064573.
  * Limisiewicz and Mareček (2020) Tomasz Limisiewicz and David Mareček.  Syntax representation in word embeddings and neural networks – a survey, 2020.
  * Linguistic Data Consortium (2013) Linguistic Data Consortium.  Ontonotes release 5.0.  https://catalog.ldc.upenn.edu/LDC2013T19, 2013.  Accessed on December 10, 2023.
  * Loshchilov and Hutter (2019) Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization, 2019.
  * Marcus et al. (1993) Mitchell P. Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini.  Building a large annotated corpus of english: The penn treebank.  _Comput. Linguist._ , 19(2):313–330, jun 1993.  ISSN 0891-2017.
  * McCloskey and Cohen (1989) Michael McCloskey and Neal J. Cohen.  Catastrophic interference in connectionist networks: The sequential learning problem.  In Gordon H. Bower, editor, _Psychology of Learning and Motivation_ , volume 24 of _Psychology of Learning and Motivation_ , pages 109–165. Academic Press, 1989.  doi: https://doi.org/10.1016/S0079-7421(08)60536-8.  URL https://www.sciencedirect.com/science/article/pii/S0079742108605368.
  * McDonald et al. (2013) Ryan McDonald, Joakim Nivre, Yvonne Quirmbach-Brundage, Yoav Goldberg, Dipanjan Das, Kuzman Ganchev, Keith Hall, Slav Petrov, Hao Zhang, Oscar Täckström, Claudia Bedini, Núria Bertomeu Castelló, and Jungmee Lee.  Universal Dependency annotation for multilingual parsing.  In Hinrich Schuetze, Pascale Fung, and Massimo Poesio, editors, _Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 92–97, Sofia, Bulgaria, August 2013. Association for Computational Linguistics.  URL https://aclanthology.org/P13-2017.
  * Miller (2000) Earl K Miller.  The prefontral cortex and cognitive control.  _Nature reviews neuroscience_ , 1(1):59–65, 2000.
  * Parker et al. (2023) Liam Parker, Emre Onal, Anton Stengel, and Jake Intrater.  Neural collapse in the intermediate hidden layers of classification neural networks, 2023.
  * Pastötter et al. (2008) Bernhard Pastötter, Karl-Heinz Bäuml, and Simon Hanslmayr.  Oscillatory brain activity before and after an internal context change - evidence for a reset of encoding processes.  _NeuroImage_ , 43:173–81, 08 2008.  doi: 10.1016/j.neuroimage.2008.07.005.
  * Pradhan et al. (2012) Sameer Pradhan, Alessandro Moschitti, Nianwen Xue, Olga Uryupina, and Yuchen Zhang.  CoNLL-2012 shared task: Modeling multilingual unrestricted coreference in OntoNotes.  In Sameer Pradhan, Alessandro Moschitti, and Nianwen Xue, editors, _Joint Conference on EMNLP and CoNLL - Shared Task_ , pages 1–40, Jeju Island, Korea, July 2012. Association for Computational Linguistics.  URL https://aclanthology.org/W12-4501.
  * Ramkumar et al. (2023) Vijaya Raghavan T. Ramkumar, Elahe Arani, and Bahram Zonooz.  Learn, unlearn and relearn: An online learning paradigm for deep neural networks, 2023.
  * Rangamani et al. (2023) Akshay Rangamani, Marius Lindegaard, Tomer Galanti, and Tomaso A Poggio.  Feature learning in deep classifiers through intermediate neural collapse.  In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pages 28729–28745. PMLR, 23–29 Jul 2023.  URL https://proceedings.mlr.press/v202/rangamani23a.html.
  * Raparthy et al. (2023) Sharath Chandra Raparthy, Eric Hambro, Robert Kirk, Mikael Henaff, and Roberta Raileanu.  Generalization to new sequential decision making tasks with in-context learning, 2023.
  * Ratcliff (1990) Roger Ratcliff.  Connectionist models of recognition memory: constraints imposed by learning and forgetting functions.  _Psychological review_ , 97 2:285–308, 1990.  URL https://api.semanticscholar.org/CorpusID:18556305.
  * Reddy (2023) Gautam Reddy.  The mechanistic basis of data dependence and abrupt learning in an in-context classification task, 2023.
  * Rougier et al. (2005) Nicolas P Rougier, David C Noelle, Todd S Braver, Jonathan D Cohen, and Randall C O’Reilly.  Prefrontal cortex and flexible cognitive control: Rules without symbols.  _Proceedings of the National Academy of Sciences_ , 102(20):7338–7343, 2005.
  * Rumbelow and Watkins (2023) Jessica Rumbelow and Matthew Watkins.  Solidgoldmagikarp (plus, prompt generation).  _LessWrong_ , 2023.  URL https://www.lesswrong.com/posts/aPeJE8bSo6rAFoLqg/solidgoldmagikarp-plus-prompt-generation.
  * Russin et al. (2022) Jacob Russin, Maryam Zolfaghar, Seongmin A Park, Erie Boorman, and Randall C O’Reilly.  A neural network model of continual learning with cognitive control.  In _CogSci… Annual Conference of the Cognitive Science Society. Cognitive Science Society (US). Conference_ , volume 44, page 1064. NIH Public Access, 2022.
  * Russin et al. (2024) Jacob Russin, Ellie Pavlick, and Michael J Frank.  Human curriculum effects emerge with in-context learning in neural networks.  _arXiv preprint arXiv:2402.08674_ , 2024.
  * Räuker et al. (2023) Tilman Räuker, Anson Ho, Stephen Casper, and Dylan Hadfield-Menell.  Toward transparent ai: A survey on interpreting the inner structures of deep neural networks, 2023.
  * Sellam et al. (2021) Thibault Sellam, Steve Yadlowsky, Jason Wei, Naomi Saphra, Alexander D’Amour, Tal Linzen, Jasmijn Bastings, Iulia Turc, Jacob Eisenstein, Dipanjan Das, Ian Tenney, and Ellie Pavlick.  The multiberts: BERT reproductions for robustness analysis.  _CoRR_ , abs/2106.16163, 2021.  URL https://arxiv.org/abs/2106.16163.
  * Singh et al. (2023) Aaditya K Singh, Stephanie C.Y. Chan, Ted Moskovitz, Erin Grant, Andrew M Saxe, and Felix Hill.  The transient nature of emergent in-context learning in transformers.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.  URL https://openreview.net/forum?id=Of0GBzow8P.
  * Srivastava et al. (2014) Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.  Dropout: A simple way to prevent neural networks from overfitting.  _Journal of Machine Learning Research_ , 15(56):1929–1958, 2014.  URL http://jmlr.org/papers/v15/srivastava14a.html.
  * Taha et al. (2021) Ahmed Taha, Abhinav Shrivastava, and Larry Davis.  Knowledge evolution in neural networks, 2021.
  * Tenney et al. (2019) Ian Tenney, Dipanjan Das, and Ellie Pavlick.  BERT rediscovers the classical NLP pipeline.  In Anna Korhonen, David Traum, and Lluís Màrquez, editors, _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4593–4601, Florence, Italy, July 2019. Association for Computational Linguistics.  doi: 10.18653/v1/P19-1452.  URL https://aclanthology.org/P19-1452.
  * Turc et al. (2019) Iulia Turc, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Well-read students learn better: On the importance of pre-training compact models, 2019.
  * van der Maaten and Hinton (2008) Laurens van der Maaten and Geoffrey Hinton.  Visualizing data using t-sne.  _Journal of Machine Learning Research_ , 9(86):2579–2605, 2008.  URL http://jmlr.org/papers/v9/vandermaaten08a.html.
  * Zhou et al. (2022) Hattie Zhou, Ankit Vani, Hugo Larochelle, and Aaron Courville.  Fortuitous forgetting in connectionist networks, 2022.
  * Zhu et al. (2015) Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler.  Aligning books and movies: Towards story-like visual explanations by watching movies and reading books.  In _2015 IEEE International Conference on Computer Vision (ICCV)_ , pages 19–27, 2015.  doi: 10.1109/ICCV.2015.11.

##  Appendix A Appendix / supplemental material

###  A.1 Probing Setup

We provide probing background in this section, borrowing some notation from
Elazar et al. [2020].

Given a set of labeled data of points $X=x_{1},\ldots x_{n}$ and task labels
$Y=y_{1},\ldots,y_{n}$, we analyze a model $f$ that predicts the labels $Y$
from $X:\hat{y_{i}}=f(x_{i})$. We assume that this model is composed of two
parts: (1) an encoder $h$ that transforms input $x_{i}$ into a learned
representation vector $\textbf{h}_{x_{i}}$ and (2) a classifier $c$ that is
used for predicting $\hat{y_{i}}$ based on $\textbf{h}_{x_{i}}$, such that
$\hat{y_{i}}=c(h(x_{i}))$. We refer by probe to the classifier $c$ and refer
by model to the model from which the encoder $h$ is a subset of.

Given this setup, we evaluate a particular model’s performance across various
layers and training steps for our POS task. Each encoder $h$ is associated
with a specific training step and layer $h^{t,l}$. We probe the residual
stream after layer $l$.

In this research, we are interested in the model’s choice of strategy at a
particular time step. That is, we seek to describe the change in prediction of
$\hat{y_{i}}$ due to varying $t,l$ of encoder $h^{t,l}$. Accordingly, we fix
$c$ as a single linear fully-connected layer.

###  A.2 Structural ICL across Layers

Figure 6: We find that structural ICL is transient across all layers of
MultiBERTs (seeds 0, 1, 2 averaged). The middle layers show the most
structural ICL during early in training, whereas very early and very late
layers remain about random throughout training.

We find that structural ICL consistently approachs random levels as training
progresses across layers in the MultiBERTs. This signifies that the model
fully loses the ability to process unseen tokens as training continues. This
is likely the reason for the "glitch tokens" described in Land and Bartolo
[2024], for which LMs fail to output sensible content.

###  A.3 Pushdown Datasets

We use the train/dev splits from the English UD Treebank for the c-pos, f-pos,
and dep tasks McDonald et al. [2013]; the train/dev splits from Ontonotes-v5
in the CoNLL-2012 Shared Task format for the ner, phrase start, and phrase end
tasks Linguistic Data Consortium [2013], Pradhan et al. [2012]; the train/dev
splits from Penn Treebank-3 for the depth and dist tasks Marcus et al. [1993];
and generated token sequences for the prev, dup, and ind tasks.

We reproduce baselines from Elazar et al. [2020] to verify the correctness of
our probing setups for c-pos, f-pos, ner, dep, phrase start and phrase end and
from Hewitt and Manning [2019] for depth and dist.

###  A.4 Pushdown Signature Observation in Syntax

Figure 7: The "Pushdown Phenomenon" is observed across syntactic features,
suggesting that a transition from IC to IW strategies happens across these
features. In early steps of training, representing syntactic information
occurs in later layers, which are more contextualized. However, as training
progress, the same properties are better encoded in earlier layers due to
memorization of token-level and n-gram level information. The n-gram level
information requires attention to build, which explains why performance in
dep, depth, and dist does not propagate all the way to embeddings.

The "Pushdown Phenomenon" suggests that in early steps of training, computing
token-wise syntactic properties occurs in later layers, which have more in-
context information. However, as training progress, the same properties are
better encoded in earlier layers until only the first couple layers are
required for representing syntactic properties.

We examine whether the "Pushdown Phenomenon" exists in various syntactic
properties in BERT. To do so, we employ our probing setup (Appendix A.1) for
the tasks of named entity recognition (ner), coarse part of speech (c-pos),
fine-grained part of speech (f-pos), dependency parsing (dep), syntactic
constituency boundaries which indicate the start and end of a phrase (phrase
start, phrase end), depth in the parse tree (depth), and distance in the parse
tree (dist). We probe each property across the axes of (1) training time steps
and (2) layers. We repeat this process for three seeds of the MultiBERTs
[Sellam et al., 2021]. For all tasks, we probed all layers of MultiBERT seeds
0, 1, and 2 for timesteps from 0 to 200,000 increasing by 20,000; 200,000 to
1,000,000 increasing by 100,000; and 1,000,000 to 2,000,000 increasing by
200,000. If a specific word is composed of multiple subword tokens, we follow
Hewitt and Manning [2019] and average the encoding across tokens.

We observe the "Pushdown Phenomenon" in all our examined tasks. However, we
find that across tasks, syntactic information is "pushed down" at different
rates. Early layer accuracy increases approximately follow a pattern of
$\textit{ner}\to\textit{phrase start}\to\textit{cpos/fpos}\to\textit{phrase
end}\to\textit{dep}\to\textit{depth}\to\textit{dist}$. We leave it to future
work to explore whether this timing is a function of (1) complexity of high-
achieving rules/heuristics consistent with Belrose et al. [2024] or (2) a
naturally occurring dependency hierarchy of syntactic relationships suggestive
of implicit curriculum learning. One possible intuition for why the "Pushdown
Signature" of memorization often coincides with poor maintenance of in-context
strategies might be neural collapse [Parker et al., 2023, Rangamani et al.,
2023], although this should be further investigated by future experimentation.

###  A.5 Synthetic Data Generation Formulation

Our synthetic data generation can be formally representated as a probabilistic
context-sensitive grammar (PCSG). Mathematically, we parameterize our vanilla
PCSG (without POS ambiguity) as follows:

$\textbf{G}=(N,\Sigma,P,S,\alpha,v)$

where $N=\\{S,Q,Q_{N},Q_{A},P_{N},P_{A}\\}$ is the set of nonterminal symbols,
$\Sigma=\\{N_{init},A_{init},N_{r},A_{r},C\\}$ is the set of terminal symbols,
$S$ is the starting point (and notationally also represents sequence), and
$\alpha,v$ characterize the sampling probability distribution of our terminal
symbols. Our production rules $P$ are

$F\to\begin{cases}S\ Q_{N}\ P_{N}\\\ S\ Q_{A}\ P_{A}\end{cases}\text{with eq.
prob.}$ $\displaystyle S\to\begin{cases}N_{init}\ C\ A_{init}\\\ C\ A_{init}\
N_{init}\end{cases}\text{with eq. prob.}$ $\displaystyle
Q\to\begin{cases}Q_{N}\\\ Q_{A}\\\ \end{cases}\text{with eq. prob.}$
$\displaystyle Q_{N}\to N_{r}$ $\displaystyle Q_{A}\to A_{r}$ $\displaystyle
P_{N}\to A_{r}\ A_{r}\ A_{r}$ $\displaystyle P_{A}\to A_{r}\ N_{r}\ N_{r}$

with terminal symbols sampled from

$\displaystyle N_{init}\sim\text{Zipf}\left(\alpha,0,\frac{v}{2}-1\right)$
$\displaystyle A_{init}\sim\text{Zipf}\left(\alpha,\frac{v}{2},v-1\right)$
$\displaystyle C\to v$ $\displaystyle N_{r}\to N_{init}$ $\displaystyle
A_{r}\to A_{init}$

$N_{init}$ captures a specific token that corresponds to a token and all
references to $N_{r}$ use this token exactly, enforcing strict consistency.

Note our sampling distribution Zipf is a truncated Zipfian parameterized by
the tuple $(\alpha,s,e)$ with a probability mass function of

$\mathbb{P}(X=k)=\frac{k^{-\alpha}}{H(\alpha,e-s)}\text{ for
}k=s,s+1,\ldots,e,\text{ where }H(\alpha,n)=\sum_{k=1}^{n}k^{-\alpha}$

We select tokens for
$\texttt{<noun>}\in\left\\{0,1,\ldots\frac{v}{2}-1\right\\}$ and
$\texttt{<adj>}\in\left\\{\frac{v}{2},\frac{v}{2}+1,\ldots v-1\right\\}$.
Thus, given a particular vocabulary size $v$ and Zipf parameter $\alpha$,
$\texttt{<noun>}\sim\text{Zipf}\left(\alpha,0,\frac{v}{2}-1\right)$ and
$\texttt{<adj>}\sim\text{Zipf}\left(\alpha,\frac{v}{2},v-1\right)$. To add
further control to this setting, we introduce the parameter $\varepsilon$ to
describe ambiguity in the solution - that is, a proportion of $\varepsilon$
tokens in each of $n=10$ bins grouped by probability mass do not have a fixed
POS but instead may be a noun or adjective with equal likelihood.

Note that when $\alpha=0$, this distribution degenerates into
$\text{Unif}(s,e)$ and when $\varepsilon=0$, each token has a fixed identity.

###  A.6 Toy Model

We employ a 6-layer BERT model across the synthetic setting experiments.
Experiments were performed with an MLM as far less prior work has examined
syntactic tasks with autoregressive models. Structure is much more difficult
to intuit in autoregressive models as they are only exposed to an ordered
subset of the tokens in a sentence. This model has 1 attention head per layer,
64-dimensional hidden dimensions, 128-dimensional intermediate
representations, and tied weights for the embedding and unembedding layers. We
optimize model parameters with AdamW with a learning rate of $5\times 10^{-5}$
[Loshchilov and Hutter, 2019]. We chose a thin and long representation to
examine how representations evolve after each attention operation (for better
granularity). The hidden dimension sizes were decided per a minimax strategy,
i.e. this representation dimensionality was the smallest such that we achieved
near perfect accuracy on a validation set for the downstream task. Future work
should better examine the effect of representation size on in-context vs. in-
weights learning.

###  A.7 Performance by Token Decile

Figure 8: Increased weight decay has little/no effect on the failure of the
structural ICL strategy (we increase weight decay from 0.01 to 0.1). In
contrast, active temporary forgetting boosts rare token validation accuracy
significantly, as seen in the tail of the distribution. Parameters are
$v=10000,\varepsilon=0.10,\alpha=1.5$

We find that on highly skewed distributions, the tail of the distribution
suffers immensely due to undertraining. This phenomenon cannot be rectified by
Singh et al. [2023]’s method of promoting asymptotic ICL. However, we find
that both active forgetting and temporary forgetting correct this behavior to
boost performance on tail tokens in skewed distributions from near-zero to
near-perfect levels.

###  A.8 Ambiguity ($\varepsilon$) Experiments

Figure 9: (Top) $\varepsilon=0.01$, (Middle) $\varepsilon=0.10$, (Bottom)
$\varepsilon=0.50$. Overall in-context strategy is dependent by amount of
ambiguity in the labels. With 50% of the tokens as ambiguous, all unambiguous
tokens use an in-context strategy; with 10%, there is a mixed strategy
dependent on where in the distribution the example is; with 1%, almost
unambiguous tokens use a memorized strategy. The vocab size is $v=10000$

In all of our ambiguity experiments, structural ICL is transient (even whe 50%
of tokens are ambiguous). The ambiguity parameter significantly alters the
models overall strategy. With a low ambiguity parameter, the model prefers
memorization (IWL strategy) of umambiguous tokens and with a high ambiguity
parameter, the model prefers an ICL strategy. Across all ambiguity parameters,
there is a difference in tail and head behavior.

###  A.9 Vocabulary Size ($v$) Experiments

Figure 10: (Top) $v=1000$, (Middle) $v=10000$, (Bottom) $v=20000$. The
strength of an in-context solution depends on the interaction between
vocabulary size $v$ and skewedness of the distribution $\alpha$. Too small of
a vocabulary size (i.e. $v=1000$) encourages more memorization in general but
fixes performance in $\alpha=1.5$ setting. The ambiguity is
$\varepsilon=0.10$.

In all of our vocabulary experiments, structural ICL is transient. As
expected, we find that vocabulary size has a similar effect to the skewedness
of the distribution. That is, increasing the vocabulary without bound would
lead to poor tail ICL performance. Too small of a vocabulary size seems to
increase ICL among very skewed distributions but decrease ICL among all other
distributions.

###  A.10 Principle Component Analysis of Embeddings

Figure 11: Vanilla training imposes structure on the adjectives and nouns such
that randomly initialized (unseen) tokens are out-of-distribution whereas
active forgetting embeddings resemble the initial distribution. Parameters
used are $v=10000,\alpha=1.0001,\varepsilon=0.10$.

We find that while vanilla training results in embeddings that lie on a
manifold, active forgetting results in embeddings that look similar to the
initial distribution. This helps motivate our use of temporary forgetting as
we would like to preserve embedding structure. Moreover, note that in the
above figure we use $\alpha=1.0001$ and PCA whereas in Figure 1 (Bottom
Right), we use $\alpha=1.5$ and T-SNE. The tail tokens in the higher skew
distribution see fewer gradient updates and thus resemble the randomly
initialized (unseen) tokens more (in addition to T-SNE likely being a better
visualization tool).

Figure 12: Vanilla training learns to partition noun and adjective embeddings
in the head of the distribution, and some structure in the tail. Active
forgetting learns no separation between noun and adjective embeddings.
Temporary forgetting learns structure in the head of the distribution and no
structure in the tail of the distribution. Parameters used are
$v=10000,\alpha=1.2,\varepsilon=0.10$.

###  A.11 Other Random Distribution Generalization

Note that while we define structural in-context learning as free from reliance
on any encoded semantic information, it is important to note that this does
not mean that structural in-context learning assumes no geometry of the space.
In fact, this would be practically impossible to achieve because connectionist
networks function in a geometric space and take advantage of orthogonality,
translation, scaling, etc. If we cannot make assumptions about the
distribution from which the data is sampled, then we deprive our networks of
their toolbox. Still, we test on random sampling distributions for the
embeddings other than our initialization distribution. Namely, we test on a
uniform distribution from 0 to 1 and a large normal distribution with mean of
5 and standard deviation of 5.

Figure 13: Vanilla training fails on all random tokens, whereas
active/temporary forgetting succeed on the random distribution of
initialization. Active and stop forgetting do not generalize to arbitrary
random distributions, although show some generalization to normal
distributions with large means and variances.

###  A.12 Required Compute for Experiments

We employed compute resources at a large academic institution. We scheduled
jobs with SLURM. For our naturalistic experiments, each MultiBERT seed
required 24 separate runs (one per tested checkpoint at a particular
timestep), which totaled $\approx$ 100 hours on an RTX A5000 with 24 GB of GPU
memory. Over 3 seeds, this was $\approx$ 300 hours of GPU usage. For our
synthetic setting, the vanilla training required 64 separate runs (one per
hyperparameter combination of vocab size, ambiguity, and sampling
distribution), which totaled $\approx$ 250 hours of RTX A5000 usage. Likewise,
our active forgetting and temporary forgetting interventions took a similar
amount of GPU usage. Therefore, in total, our GPU usage for all synthetic
experiments summed up to about 750 hours. We ran experiments mostly in
parallel with SLURM to iterate quickly. Compute was a significant limitation
for the development time and informed our development of training
interventions in a synthetic setting. In total, our GPU usage was
significantly higher than the reported number due to various failed/modified
experiments. The total compute likely was around 20,000 GPU-hours on RTX
A5000s, although this is a rough estimate.