<EMAIL_ADDRESS>WeydeResearch Centre for Machine Learning,
Department of Computer Science, City, University of London, United Kingdom
<EMAIL_ADDRESS>Manisha Kopparti††thanks: Funded by a PhD
studentship from City, University of LondonResearch Centre for Machine
Learning, Department of Computer Science, City, University of London, United
Kingdom

We would like to thank the anonymous reviewers of this article for their
valuable comments and suggestions that helped to improve this article.

# Modelling Identity Rules with Neural Networks

###### Abstract

In this paper, we show that standard feed-forward and recurrent neural
networks fail to learn abstract patterns based on identity rules. We propose
Relation Based Pattern (RBP) extensions to neural network structures that
solve this problem and answer, as well as raise, questions about integrating
structures for inductive bias into neural networks.

Examples of abstract patterns are the sequence patterns ABA and ABB where A or
B can be any object. These were introduced by Marcus et al (1999) who also
found that 7 month old infants recognise these patterns in sequences that use
an unfamiliar vocabulary while simple recurrent neural networks do not. This
result has been contested in the literature but it is confirmed by our
experiments. We also show that the inability to generalise extends to
different, previously untested, settings.

We propose a new approach to modify standard neural network architectures,
called Relation Based Patterns (RBP) with different variants for
classification and prediction. Our experiments show that neural networks with
the appropriate RBP structure achieve perfect classification and prediction
performance on synthetic data, including mixed concrete and abstract patterns.
RBP also improves neural network performance in experiments with real-world
sequence prediction tasks.

We discuss these finding in terms of challenges for neural network models and
identify consequences from this result in terms of developing inductive biases
for neural network learning.

##  1 Introduction

Despite the impressive development of deep neural networks over recent years,
there has been an increasing awareness that there are some tasks that still
elude neural network learning or need unrealistic amounts of data. Humans, on
the other hand, are remarkably quick at learning and abstracting from very few
examples. Marcus [1] showed in an experiment that 7-month old infants already
recognise sequences by identity rules, i.e. which elements are repeated, after
just two minutes of familiarization. In that study a simple recurrent neural
network model was also tested and it failed to generalise these identity rules
to new data.

In this study, we re-visit this problem and evaluate the performance of
frequently used standard neural network models in learning identity rules.
More specifically, we find that feed-forward and recurrent neural networks
(RNN) and their gated variants (LSTM and GRU) in standard set-ups clearly fail
to learn general identity rules presented as classification and prediction
tasks.

We tackle this problem by proposing _Relation Based Patterns_ (RBP), which
model identity relationships explicitly as extensions to neural networks for
classification and prediction. We show experimentally that on synthetic data
the networks with suitable RBP structures learn the relevant rules and
generalise with perfect classification and prediction. We also show that this
perfect performance extends to mixed rule-based and concrete patterns, and
that RBP improves prediction on real-world language and music data.

Identity rules are clearly in the hypothesis space of the neural networks, but
the networks fail to learn them by gradient descent. We identify that both the
comparison of related input neurons and of input tokens needs to be predefined
in the network to learn general rules from data. The RBP structures introduce
this inductive bias in the neural networks and thus enable the learning of
identity rules by standard neural networks.

Our contributions in this paper are specifically:

  * •

we evaluate several common NN architectures: feed-forward networks, RNN, GRU,
and LSTM, in novel settings, and find that they fail to learn general identity
rules;

  * •

we identify reasons that prevent the learning process from being successful in
this context;

  * •

we propose the Relation Based Patterns, a new method to enable the learning of
identity rules within the regular network structure;

  * •

we show in experiments that identity rules can be learnt with RBP structure on
artificial data, including mixed rule-based and concrete patterns, and that
they improve performance in real-world prediction tasks;

The remainder of this paper is structured as follows. Section 2 introduces
related work on modelling identity rules. Section 3 presents results of our
experiments with standard neural network architectures. Section 4 presents our
RBP model and its different variants. Section 5 presents the results of
experiments using RBP structures. Section 6 addresses the application of RBP
to mixed patterns and real data. Section 7 discusses the implications of the
presented experimental results and Section 8 concludes this paper.

##  2 Related work

Our task is the learning of rules from sequential data. This is often seen as
grammar learning, on which there have been many studies in psychology. [2]
made an early contribution on implicit learning and generalisation.
Subsequently, [3, 4] studied specifically the knowledge acquired during
artificial grammar learning tasks. ]

The specific problem we are addressing in this study is the recognition of
abstract patterns that are defined by the identity relation between tokens in
a sequence. In the well-known experiments by [1], infants were exposed to
sequences of one of the forms _ABA_ or _ABB_ , e.g. ‘la di la’ or ‘la di di’,
for a few minutes in the familiarisation phase.

In the test phase the infants were exposed to sequences with a different
vocabulary (e.g. ‘ba tu ba’ and ‘ba tu tu’) and they showed significantly
different behaviour depending on whether the sequences exhibited the form they
were familiarised with or not.

This type of pattern only depends on the equality between elements of the
sequence and after successful learning it should be recognisable independently
of the vocabulary used. However, [1] also showed that simple recurrent Elman
networks were not able to perform this learning task. This finding sparked an
exchange about whether human speech acquisition is based on rules or
statistics and the proposal of several neural networks models that claimed to
match the experimental results. [5] and [6] proposed a solution based on a
distributed representation of the input and on pre-training where the network
is first trained to recognise repeated items in a sequence. The network is
subsequently trained on classifying ABA vs ABB patterns. Only [6] reports
specific results and has only 4 test data points, but 100% accuracy. However,
[7] reported that they could not recreate these results.

[8] and [9] suggested solutions which are based on modified network
architectures and training methods. [10] could not replicate the results by
[9] and found that the models by [8] do not generalise. The claims by [10]
were again contested by [11]. A number of other methods were suggested that
used specifically designed network architectures, data representations, and
training methods, such as [12, 13, 14, 15]. More recent work by [16] suggests
that prior experience or pre-defined context representation (“pre-training” or
“pre-wiring”) is necessary for the network to learn general identity rules
when using echo state networks. While these works are interesting and
relevant, they do not answer our question whether more commonly used network
architectures can learn general identity rules.

The discussion of this problem is part of a wider debate on the systematicity
of language learning models, which started in the 1980s and 1990s [17, 18].
This debate, like the more specific one on identity rules, has been
characterised by claims and counter-claims [19, 20, 21, 22, 23, 24], which, as
stated by [25], often suffer from a lack of empirical grounding. Very
recently, the work in [26] has defined a test of systematicity in a framework
of translation, applied it to standard _seq2seq_ neural network models [27].
They found that generalisation occurs in this setting, but it depends largely
on the amount and type of data shown, and does not exhibit the extraction and
systematic application of rules in the way a human learner would.

In most of the studies above, the evaluation has mostly been conducted by
testing whether the output of the network shows a statistically significant
difference between inputs that conform to a trained abstract pattern and those
that do not. From a machine learning perspective, this criterion is not
satisfactory as we, like [26], would expect that an identity rule should
always be applied correctly once if it has been learned from examples, at
least in cases of noise-free synthetic data. We are therefore interested in
the question whether and how this general rule learning can be achieved with
common neural network types for sequence classification.

This question also relates to recent discussions sparked by [28] about deep
neural networks’ need for very large amounts of training data, lack of
robustness and lack of transparency as also expressed, e.g., by [29, 30, 31].
We surmise that these issues relate to the lack of generalisation beyond the
space covered by the input data, i.e. extrapolation, which is generally seen
as requiring an inductive bias in the learning system, but there is no general
agreement about the nature or implementation of inductive biases for neural
networks, e.g. [32, 33]. In recent years, there was a trend to remove human
designed features from neural networks, and leave everything to be learned
from the data [34]. We follow here the inverse approach, to add a designed
internal representation, as we find that for the given problem standard neural
network methods consistently fail to learn any suitable internal
representation from the data.

##  3 Experiment 1: standard neural networks

We test different network architectures to evaluate if and to what extent
recurrent and feed-forward neural networks can learn and generalise abstract
patterns based on identity rules.

###  3.1 Supervised learning of identity rules

The problem in the experiment by [1] is an unsupervised learning task, as the
infants in the experiments were not given instructions or incentives. However,
most common neural network architectures are designed for supervised learning
and there are also natural formulations of abstract pattern recognition as
supervised learning task in the form of classification or prediction.

In our case, abstract patterns are defined by identity relations. Expressed in
logic, they can be described using the binary equality predicate
$eq(\cdot,\cdot)$. For a sequence of three tokens $\alpha,\beta,\gamma$ the
rule-based patterns $ABA$ and $ABB$ can be described by the following rules:

$\displaystyle ABA$ $\displaystyle:\neg eq(\alpha,\beta)\land
eq(\alpha,\gamma)$ (1) $\displaystyle ABB$ $\displaystyle:\neg
eq(\alpha,\beta)\land eq(\beta,\gamma).$ (2)

These rules are independent of the actual values of
$\alpha,\beta,\text{and}\;\gamma$ and also called abstract patterns. Concrete
patterns, on the other hand, are defined in terms of values of from a
vocabulary $a,b,c,...$ . E.g., sequences $a**$, i.e. beginning with ‘$a$’, or
$*bc$, ending with ‘$bc$’, can be formulated in logic as follows:

a** $\displaystyle:\alpha=\mlq{}a\mrq$ (3) *bc
$\displaystyle:\beta=\mlq{}b\mrq\land\gamma=\mlq{}c\mrq.$ (4)

For the remainder of this article we use the informal notations $ABA$ and
$a**$ as far as they are unambiguous in their context.

For classification, the task is to assign a sequence to a class, i.e. _ABA_ or
_ABB_ , after learning from labelled examples. For prediction, the task is to
predict the next token given a sequence of two tokens after exposure to
sequences of one of the classes (e.g. only ABA, or ABB respectively). These
tasks are suitable for the most commonly used neural network architectures.

###  3.2 Experimental set-up

#### Network set-up

We use the Feed-forward Neural Network (FFNN) (also called Multi-layer
Perceptron) [35], the Simple Recurrent Neural Network (RNN, also called Elman
network [36]), the Gated Recurrent Unit (GRU) network [37], and the Long Short
Term Memory (LSTM) network [38]. For Prediction we only use the RNN and its
gated variants GRU and LSTM.

The input to the networks is a one-hot encoded vector representing each token
with $n$ neurons, where $n$ is the size of the vocabulary. In the case of the
FFNN, we encode the whole sequence of 3 tokens as a vector of size $3n$. For
the recurrent models, we present the tokens sequentially, each as a
$n$-dimensional vector. We set the number of neurons in each hidden layer to
(10, 20, 30, 40, 50), using 1 or 2 hidden layers. We use Rectified Linear
Units (ReLUs) for the hidden layers in all networks. The output layer uses the
softmax activation function. The number of output units is 2 for
classification and the size of the vocabulary for prediction. We train with
the Adam optimisation method [39], using initial learning rates of
$0.01,0.1,0.2,0.4$, and train with the synthetic datasets in one batch. We use
regularisation with Dropout rates of 0.1, 0,2, 0.4 and set the number of
epochs to 10, within which all trainings converged.

We conduct a full grid search over all hyperparameters using four-fold cross-
validation to optimise the hyperparameters and determine test results. We run
a total of 10 simulations for each evaluation and average the results. All
experiments have been programmed in PyTorch and the code is publicly
available.111https://github.com/radhamanisha1/RBP-architecture

#### Datasets

For performing the rule learning experiments, we artificially generate data in
the form of triples for each of the experiments. We consider our sample
vocabulary as $a...l$ (12 letters) for both prediction and classification
tasks. We generate triples in all five abstract patterns: AAA, AAB, ABA, ABB,
and ABC for the experiments. The sequences are then divided differently for
the different cases of classification. For all the experiments we use separate
train, validation, and test sets with 50%, 25%, and 25% of the data,
respectively. All sampling (train/test/validation split, downsampling) is done
per simulation.

###  3.3 Classification

First we test three different classification tasks as listed below. We use
half the vocabulary for training and the other half for testing and validation
(randomly sampled). We divide the sequences into two classes as follows,
always maintaining an equal size of both classes:

  * 1)

ABA/ABB vs other: In task a) class one contains only pattern ABA while the
other contains all other possible patterns (AAA, AAB, ABB, ABC) downsampled
per pattern for class balance. The task is to detect whether
$eq(\alpha,\gamma)\land\neg eq(\alpha,\beta)$ is true or false. Analogously,
the task in b) ABB vs other is to detect $eq(\beta,\gamma)\land\neg
eq(\alpha,\beta)$. This case corresponds to the experiment in [1], where only
one rule-based pattern type is used for familiarisation.

  * 2)

ABA vs ABB: This task is like task 1 above, but only pattern ABB occurs in the
second class, so that this task has less variance in the second class. We
expected this task to be easier to learn because two equality predicates
$eq(\alpha,\gamma),eq(\beta,\gamma)$ change their values between the classes
and are each sufficient to indicate the class.

  * 3)

ABC vs other: In this case, class one (ABC) has no pair of equal tokens, while
the $other$ class has at least one of
$eq(\alpha,\beta),eq(\alpha,\gamma),eq(\beta,\gamma)$ as $true$, i.e.
detecting equalities without localising them is sufficient for correct
classification.

In our experiments, the training converged quickly in all cases and the
classification accuracy on the training data was 100%. The results on the test
set are shown in Table 1. In all cases the baseline, corresponding to random
guessing is 50%. This baseline is only exceeded for task 1) by the RNNs and
their gated variants, and even then the accuracy is far from perfect at 55%.

Classification task | FFNN | RNN | GRU | LSTM
---|---|---|---|---
1a) ABA/other | 50% | 55% | 55% | 55%
1b) ABB/other | 50% | 55% | 55% | 55%
2) ABA/ABB | 50% | 50% | 50% | 50%
3) ABC/other | 50% | 50% | 50% | 50%
Table 1: Three classification tasks based on abstract patterns over 10
simulations. The numbers show test set accuracy after a grid search and cross
validation as described in section 3.2. All values are rounded to the next
percentage point.

###  3.4 Prediction

We performed prediction experiments on two tasks. In task 1) we train and test
on ABA patterns and in task 2) on ABB. Training and test/validation set use
different vocabularies. The training converged quickly in less than 10 epochs,
and after training the classification accuracy on the training set is 100%.

The results on the test set are shown in Table 2. The baseline is
$~{}8.3\ldots\%$ as we have a vocabulary size of 12. We use again half the
vocabulary (6 values) for training and half for validation/testing. The
results show that the tested networks fail completely to make correct
predictions. They perform below the baseline at 0% accuracy, which is mostly
because they predict only tokens that appear in the training set but not in
the test set.

Prediction task | RNN | GRU | LSTM
---|---|---|---
1) ABA | 0% | 0% | 0%
2) ABB | 0% | 0% | 0%
Table 2: Prediction results for two different abstract patterns. The numbers
show test set prediction accuracy after a grid search and cross validation as
described in section 3.2.

###  3.5 Discussion

The results show clearly that FFNNs, RNNs, GRUs and LSTMs do not learn general
abstract patterns based on identity rules. This agrees with the previously
reported experiments by [1]. However, since there was some conflicting
evidence in the literature, the clarity of the outcome was not expected.

#### Questions raised

This result raises the question of why these neural networks do not learn to
generalise abstract patterns from data. There are two aspects worth
considering for an explanation: the capacity of the network and the necessary
information for the network to solve the problem.

Regarding the capacity: the solution to the task is in the hypothesis space of
the neural networks, since proofs exist of universal approximation properties
for feed-forward networks with unbounded activation functions [40] and of
Turing-completeness for recurrent networks [41]. We will present a
constructive solution below, putting that result into practice, with a design
of network instances that solve the problem.

The relevant question, as has been pointed out by [16], is therefore why
learning with backpropagation does not lead to effective generalisation here.
There are three different steps that are necessary to detect identity rules: a
comparison of input neurons, a comparison of tokens, represented by multiple
neurons, and a mapping of comparison results to classes or predictions.

#### Vocabulary hypothesis

A possible reason for the failure of the networks to generalise what we call
the vocabulary hypothesis. It is based on the separated vocabulary in one-hot
encoded representation. This leads to some input neurons only being activated
in the training set and some only in the validation and test sets.

In order to learn suitable weights for an input comparison, there would have
to be a suitable gradient of the weights of the outgoing connections from
these inputs. If parts of the vocabulary do not appear in the training data,
i.e. the activation of the corresponding input neurons is always zero during
training, the weights of their outgoing connections will not be adapted. We
therefore expect that the separation of the vocabulary prevents generalisation
from the training to the test set as the weights going out from neurons that
are used during testing have not been adapted by the gradient descent. Based
on this consideration we conducted another experiment with a shared
vocabulary.

This experiment is called ABA-BAB vs other. We again represent our vocabulary
as $a...l$ (12 letters) for this task with train/validation/test split as
$50\%/25\%/25\%$. Now we use the same vocabulary for training, validation, and
testing, but we separate different sequences of the form ABA that use the same
tokens between the training and validation/test sets. E.g., if the $ded$ is in
the test set, then $ede$ is in the training or validation set, so that there
is no overlap in terms of actual sequences. Like in classification experiment
1), training converged quickly and resulted in perfect classification
performance on the training set.

Classification task | FFNN | RNN | GRU | LSTM
---|---|---|---|---
ABA-BAB vs other | 50% | 50% | 50% | 50%
Table 3: Classification results on test sets with the same vocabulary used in
test, validation and training set.

The results on the test set presented in Table 3 show performance at the
baseline with no evidence of generalisation. This shows that activating all
inputs by using a shared vocabulary is not sufficient to enable generalisation
in the learning process.

#### Other explanations

A second potential problem is which neurons should be compared. The FFNN has
no prior information about neurons belonging to the same or different tokens
or about which input neurons correspond to the same token values. In the RNN,
one token is presented per time step, so that a comparison between the
previous hidden state and the current input is possible as the same neurons
are activated. However, with a full set of connections between the previous
hidden layer and the current, there is no reason that relations between the
same neurons at different time steps would be processed differently from
different neurons.

On the other hand, if we had a representation that includes the information of
which tokens are identical or different, then we would have all the
information we need for a mapping, as these are the relations in which our
defining rules are formulated (e.g. ABA is defined as
$eq(\alpha,\gamma)\land\neg eq(\alpha,\beta)$). This idea has led to the
Relation Based Pattern (RBP) model that we introduce in the next section and
then evaluate with respect to its effect on both abstract and concrete pattern
learning.

##  4 Design of Relation Based Pattern models

To address the inability of neural networks to generalise rules in neural
network learning, we developed the Relation Based Pattern (RBP) model as a
constructive solution, where the comparisons between input neurons and between
tokens and the mappings to outputs are added as a predefined structure to the
network. The purpose of this structure is to enable standard neural networks
to learn abstract patterns based on the identity rules over tokens while
retaining other learning abilities.

In the RBP model there are two major steps. The first step is defining
comparison units for detecting repetitions, called DR units, and the second
step is adding the DR units to the neural network.

###  4.1 Comparison units

#### Comparing neurons

We assume, as before, that input is a one-hot encoded vector of the current
token along with the $n-1$ previous vectors for a given context length n (in
this study context length 3 for classification and 2 for prediction). We use
comparison units, called DR units (differentiator-rectifier). As the name
suggests, they apply a full wave rectification to the difference between two
inputs: $f(x,y)=|x-y|$. The first level of $DR$ units are $DR_{n}$ units that
are applied to every pair of corresponding input neurons (representing the
same value) within a token representation, as shown in Figure 1.

Figure 1: $DR_{n}$ units comparing related inputs with an absolute of
difference activation function. In one-hot encoding there are $kDR_{n}$ units
for every pair of input tokens, where $k$ is the vocabulary size.

#### Comparing tokens

The next level of $DR$ units are the $DR_{p}$ units that sum the activations
of the $DR_{n}$ values that belong to one pair of tokens. Based on the
sequence length $n$ and vocabulary size $a$ we create $k=a\times n(n-1)/2$
$DR_{n}$ units for all the possible pairs of tokens and i.e. in our
classification example, we have a sequence of 3 tokens and a vocabulary size
of 12, i.e. $12\times 3(3-1)/2=36\times 3$ $DR_{n}$ units. All the $DR_{n}$
units for a pair of tokens are then summed in a $DR_{p}$ unit using
connections with a fixed weight of +1. E.g. we have $5\times(5-1)/2=10$
$DR_{p}$ units for a context of length 5. Figure 2a shows the network
structure with $DR_{n}$ and $DR_{p}$ units.

For the prediction case, we also use the same approach to represent the
difference between each input token and the next token (i.e., the target
network output). We create $n$ $DR_{p}out$ units that calculate the difference
between each input in the given context and the next token. There are $k\times
n$ $DR_{n}{out}$ units that compare the corresponding neurons for each pair of
input/output tokens, in the same way as for the pairs of input tokens. The
overall network structure is shown in Figure 2b.

(a) The $DR_{p}$ and $DR_{n}$ units that are used in the RBP1 and RBP2
structures with $3\times k$ $DR_{n}$ and 3 $DR_{p}$ units for a vocabulary
size $k$ and sequence length 3.

(b) The $DR_{out}$ structure for detecting repetitions between input and
target. The $DR_{p}out$ values are calculated at training time and a model is
trained to predict them conditional on $DR_{p}in$ (see Figure 5).

Figure 2: $DR_{n}$ and $DR_{p}$ units for inputs (all RBP) and outputs (RBP3).

###  4.2 Neural network integration

Figure 3: Overview of the RBP1n/RBP1p structure.

We combine the DR units ($DR_{n}$ and $DR_{p}$) with the neural network models
in early, mid and late fusion approaches we call RBP1, RBP2 and RBP3, as
outlined below. The weights that connect $DR_{n}$ units to input and output,
and the $DR_{n}$ to $DR_{p}$ units and the offset layer are fixed, all other
weights that appear in the following models are trainable with
backpropagation.

#### Early Fusion (RBP1n/p)

In this approach, $DR_{n}$ or $DR_{p}$ units are added as additional inputs to
the network, concatenated with the normal input. In Figure 3, the RBP1n/p
structure is depicted. We use early fusion in both the prediction and
classification tasks.

#### Mid Fusion (RBP2)

The $DR_{p}$ units are added to the hidden layer. Figure 4a shows the mid
fusion structure for the feed-forward network and Figure 4b for the recurrent
network respectively. The RBP2 approach is used for classification and
prediction tasks.

(a) RBP2a

(b) RBP2b

Figure 4: Overview of RBP2 approaches, where the $DR_{p}out$ units are
concatenated to the hidden layer.

Figure 5: Overview of the RBP3 approach. The $DR_{p}in$ values are calculated
as in RBP2. From there, we use a fully connected layer to predict $DR_{p}out$
(trained with teacher-forcing). The predicted $DR_{p}{out}$ values are mapped
back to the vocabulary (based on the context tokens) and used as probability
offsets in a mixture of experts with the standard neural network in the left
part of the diagram. All connections are trainable except $Input$ to
$DR_{p}in$ and $DR_{p}out$ to Output offsets (dotted arrows).

#### Late Fusion (RBP3)

In this approach, we use the same structure as in RBP2 (we call it $DR_{n}in$
and $DR_{p}in$ in this context), and in addition we estimate the probability
of identity relations between the input and the output, i.e., that the token
in the current context is repeated as the next token. We use a structure
called $DR_{p}out$ for this, and from there we project back to the vocabulary,
to generate a probability offset for the tokens appearing in the context.

Figure 5 gives an overview of the RBP3 late fusion scheme. The $DR_{p}in$
units detect identities between the input tokens in the current context as
before. The $DR_{p}out$ units model the identities between the context and the
next token, as shown in the Figure 4b, where repetition is encoded as 1, and a
non-repeated token as a $-1$. During training we use teacher-forcing, i.e., we
set the values of the $DR_{p}out$ units to the true values. We use a feed-
forward neural network with one hidden layer to learn a mapping from the
$DR_{in}$ to the $DR_{out}$. This gives us an estimate of the $DR_{out}$ units
given the $DR_{in}$ units. The $DR_{out}$ values are then normalised
subtracting the mean, and then mapped back to the output space (the one-hot
vocabulary representation), using a zero value for the output values that
don’t appear in the input. These output offsets are then combined in a
weighted sum (mixture of experts) with the output distribution estimated by
the standard normal network (on the left side in Figure 5). The weights in the
mixture are trainable. The outputs from the combined distribution of mixture
of experts are clipped between [0,1] and renormalised. The final output
distribution is a softmax layer providing the probability distribution over
the vocabulary for the next token.

##  5 Experiment 2: neural networks with RBP structures

In the following we repeat the experiments from section 3 but also test
networks with added RBP structures. For convenience we repeat the previous
results in the tables in this section.

###  5.1 Classification experiments

This experiment is analogous to the first classification experiment. In the
case of the feed-forward network, RBP2(a) was used in the mid fusion approach
and for recurrent network, RBP2(b) was used. We trained again for 10 epochs
and all networks converged to perfect classification on the training set.
Table 4 provides the overall test accuracy for the three approaches.

Task | RBP | FFNN | RNN | GRU | LSTM
---|---|---|---|---|---
1a) ABA vs other | - | 50% | 55% | 55% | 55%
RBP1n | 50% | 55% | 55% | 55%
RBP1p | 65% | 70% | 70% | 70%
RBP2 | 100% | 100% | 100% | 100%
1b) ABB vs other | - | 50% | 55% | 55% | 55%
RBP1n | 50% | 55% | 55% | 55%
RBP1p | 65% | 70% | 70% | 70%
RBP2 | 100% | 100% | 100% | 100%
2) ABA vs ABB | - | 50% | 50% | 50% | 50%
RBP1n | 50% | 60% | 65% | 65%
RBP1p | 75% | 75% | 75% | 75%
RBP2 | 100% | 100% | 100% | 100%
3) ABC vs other | - | 50% | 50% | 50% | 50%
RBP1n | 55% | 65% | 65% | 65%
RBP1p | 55% | 70% | 70% | 70%
RBP2 | 100% | 100% | 100% | 100%
4) ABA-BAB vs other | - | 50% | 50% | 50% | 50%
RBP1n | 55% | 72% | 75% | 75%
RBP1p | 69% | 74% | 75% | 76%
RBP2 | 100% | 100% | 100% | 100%
Table 4: Classification experiments with RBP: test accuracy for the different
models and tasks, as explained above. Results with ‘-’ in the RBP column are
the same as in section 3 and shown here again for comparison.

The results with RBP1n models already show some improvement over the baseline
in most configurations, but the result are only slightly above the standard
networks, with RNNs, GRUs and LSTMs benefiting more than FFNN. This supports
our hypothesis that learning to compare corresponding input neurons is a
challenging task for neural networks. However, the results show that providing
that comparison is not sufficient for learning identity rules.

RBP1p structures also aggregate all the $l$ $DR_{n}$ neurons that belong to a
pair of input tokens. The results show that providing that information leads
to improved accuracy and provide evidence that this aggregation is another
necessary step that the networks do not learn reliably from the data.

The RBP2 models enable the neural networks to make predictions and
classifications that generalise according to identity rules that it learns
from data. The RBP2 leads to perfect classification for all network types
tested. This confirms the design consideration that comparing pairs of tokens
provides the relevant information in the form required for classification, as
the classes are defined by $equals$ relations, so that the activations of the
DRp units are directly correlated with the class labels.

A surprising result is the big difference between the generalisation using the
RBP1p and the RBP2 structures. They both provide the same information, only in
different layers of the network, but RBP1p only reaches at most 75% with a 50%
baseline. We hypothesize that the additional expressive power provided by the
non-linearities in the hidden layer here provides effective learning. This
effect deserves further investigation.

###  5.2 Prediction experiments

Here we performed two experiments separately on ABA and ABB patterns as in
experiment 1 on prediction. The tasks are the same as previously and we
trained again for 10 epochs after which all networks had converged to perfect
prediction accuracy on the training data. Table 5, summarises the accuracy for
RNN, GRU and LSTM without RBP, and with RBP1n, 1p, 2, and 3.

Pattern | RBP | RNN | GRU | LSTM
---|---|---|---|---
1) ABA | - | 0% | 0% | 0%
RBP1n | 0% | 0% | 16%
RBP1p | 0% | 0% | 18%
RBP2 | 0% | 0% | 20%
RBP3 | 100% | 100% | 100%
2) ABB | - | 0% | 0% | 0%
RBP1n | 0% | 0% | 17%
RBP1p | 0% | 0% | 20%
RBP2 | 0% | 0% | 22%
RBP3 | 100% | 100% | 100%
Table 5: Test set accuracy in prediction experiments for patterns ABA and ABB.
As before, results are averaged over 10 simulations and rounded to the nearest
decimal point. Results with ‘-’ in the RBP column are the same as in section 3
and shown here again for comparison.

Overall, we observe that only the LSTM benefits from RPB1n, RBP1p, and RBP2
structures, all other networks can apparently not make use of the information
provided. The RBP3 model, on the other hand, leads to perfect classification
on our synthetic dataset.

Our interpretation is, that standard recurrent networks do not learn the more
complex mapping that prediction requires, as not only recognition of a pattern
but also selecting a prediction on the basis of that pattern is required. The
somewhat better results of the LSTM networks are interesting. In the RBP3
model, the mapping between the identity patterns and back to the vocabulary
adds considerable prior structure to the model and it is very effective in
achieving the generalisation of rule-based patterns.

##  6 Experiment 3: mixed tasks and real data

The results presented here were all obtained with synthetic data where
classification was exclusively on rule-based abstract patterns. This raises
the question whether the RBP will impede recognition of concrete patterns in a
mixed situation. Furthermore, we would like to know whether RBP is effective
with real data where the abstract and concrete patterns may interact.

###  6.1 Mixed abstract and concrete patterns

We conducted an experiment where the classes were defined by combinations of
abstract and concrete patterns. Specifically we defined 4 classes based on the
abstract patterns $ABA$ and $ABB$ combined with the concrete patterns $a**$
and $b**$. E.g., the class $ABA,a**$ can be expressed logically as

$eq(\alpha,\gamma)\land\neg eq(\alpha,\beta)\land\alpha=`a\mrq.$ (5)

We use a vocabulary of 18 characters, out of which 12 are used for training
and 6 are used for validation/testing in addition to ‘a’ and ‘b’, which need
to appear in all sets because of the definition of the concrete patterns. For
class 1/3 and class 2/4, abstract patterns ABA and ABB are used respectively.
Class 1/2 and 3/4 start with tokens ‘a’ and ‘b’ respectively. The train,
validation and test split is 50%, 25%, and 25% respectively. We trained the
network for 10 epochs, leading to perfect classification on the training set.
A total of 10 simulations has been performed. We test a feed forward and a
recurrent neural network without and with RBP1p and RBP2. The results are
shown in Table 6.

RBP | FFNN | RNN
---|---|---
- | 23% | 42%
RBP1p | 49% | 57%
RBP2 | 100% | 100%
Table 6: Test set accuracy for mixed abstract/concrete pattern classification.

As in the previous experiments, networks without RBP fail to generalise the
abstract patterns. The results for RBP1p and RBP2 show, that the ability to
learn and recognise the concrete patterns is not impeded by adding the RBP
structures.

###  6.2 Language models with RBP

In order to test the capability of networks with RBP structure, we use them in
two language modelling tasks. One is to predict characters in English text,
and one is to predict the pitch of the next note in folk song melodies. We
selected both tasks because of the prevalence of repetitions in the data, as
notes in music and characters in English tend to be repeated more than words.
Our RBP structures are designed to model identity-rules and we therefore
expect them to be more effective on tasks with more repetitions.

#### Character prediction

We conducted a character prediction experiment on a subset of the Gutenberg
electronic book collection222https://www.gutenberg.org/, consisting of text
with the dataset size of 42252 words. We used 2 hidden layers with 50 neurons
each. In the RBP2 model, the DRp units were concatenated with the first hidden
layer. The learning rate is set to 0.01 and the network training converged
after 30 epochs. Each character is predicted without and with the RBP variants
using a context size of 5. The prediction results are summarized in Table 7.

RBP | RNN | GRU | LSTM
---|---|---|---
- | 3.8281 | 3.8251 | 3.8211
RBP1p | 4.4383 | 4.4368 | 4.4321
RBP2 | 3.7512 | 3.7463 | 3.7448
RBP3 | 3.4076 | 3.4034 | 3.4012
Table 7: Character prediction task. The numbers show the average cross entropy
loss per character on the test set (lower is better, best values are set in
bold), without and with RBP structures using context length 5.

#### Pitch prediction

In another experiment we applied RBP to pitch prediction in melodies [42]
taken from the Essen Folk Song Collection [43]. We performed a grid search for
each context length for hyper parameter tuning, with [10,30,50,100] as the
size of the hidden layer and [30,50] epochs with learning rate set to 0.01
with one hidden layer. The results for context length 5 are summarized in
Table 8. RBP improved the network performance for RNN, GRU, and LSTM. Overall,
LSTM with late fusion produces the best result and also improves over the best
reported performance in pitch prediction with a long-term model on this
dataset with a cross-entropy of 2.547, which was achieved with a feature
discovery approach by [44].

RBP | RNN | GRU | LSTM
---|---|---|---
- | 2.6994 | 2.5702 | 2.5589
RBP1p | 2.6992 | 2.5714 | 2.5584
RBP2 | 2.6837 | 2.5623 | 2.5483
RBP3 | 2.6588 | 2.5549 | 2.5242
Table 8: Pitch prediction task on the Essen Folk Song Collection. The numbers
show the average cross entropy per note (lower is better, best values are set
in bold), without and with RBP using context length 5.

#### Results

In both character and pitch prediction, the addition of RBP3 structures
improves the overall results consistently. RBP1n leads to a deterioration in
character prediction and to inconsistent effect on pitch prediction, while
RBP2 leads to a slight but consistent improvement in both tasks. This provides
further evidence that the RBP structure enables the learning of relevant
patterns in the data.

##  7 Discussion

###  7.1 Standard neural networks

The results of the experiments described above confirm the results of [1] and
others that standard recurrent (and feed-forward) neural networks do not learn
generalisable identity rules. From the tested models and settings of the task
we can see that the lack of activation of input neurons impedes learning, but
avoiding this lack is not sufficient. The task assumes that the identity of
input tokens is easy to recognise, classify and base predictions on, but the
models we tested do not learn to generalise in this way. These results confirm
our view that in order to generalise it is necessary to know which input
neurons are related, similarly on the next level, which comparisons of input
belong to a pair of tokens so that they can be aggregated per token. The
structure of neural networks does not provide any prior preference for inputs
that are related in this way over any other combinations of inputs. This makes
it seem plausible that the solutions by [5, 6, 9] could not be replicated by
[7, 10].

###  7.2 Constructive model with RBP

The RBP model addresses the learning of identity rules by adding neurons and
connections with fixed weights. From the input neurons we add connections to a
DR (differentiator-rectifier) unit from each pair of corresponding input
neurons within any pair of tokens (represented in one-hot encoding). These DR
units calculate the absolute of the difference of the activations of the two
input neurons. They are followed by $DRp$ units that aggregate by taking the
sum of the DR unit activations for each pair of tokens. The fact that the DRp
units relate to the difference between each pair of neurons makes the learning
task for classification much simpler, as has been confirmed by our results. An
open question in this context is why the RBP2 is so much more effective than
RBP1p for classification, although the only difference is the layer in which
the information is added into the network.

For prediction, we need a more complex structure, as beyond recognition of
identity, also the selection of the token to predict is required, that depends
on the tokens in the context and their similarity relations. The constructive
RBP solution requires a transformation into a representation of identity
relations in the input that is mapped to identities between input and output
and that is mapped back to the token space by adding prediction probability to
the tokens that are predicted to be identical between input and output. This
created a complex predefined structure, but without it even the models that
achieved prefect classification failed to make correct predictions with new
data. Only the LSTM models could use the RPB1 and RBP2 information to make
prediction above the baseline (22% vs 8.3%). We hypothesise that the gating
structure of the LSTMs enables at least some effective mapping. The 100%
correct predictions by all models using RBP3 shows the effectiveness of this
structure.

###  7.3 Applications

Adding a bias into the network with a predefined structure such as RBP raises
the question whether there is a negative effect on other learning abilities of
the network and whether interactions between the abstract and concrete tasks
can be learnt. In the mixed pattern experiment, RBP is still effective and
showed no negative effect. In experiments with real language and music data we
found that RBP3 has a positive effect on the prediction of characters in
language and pitches in folk song melodies. The small negative effect of RBP1
on character prediction seems to indicate that there may be confounding effect
where identity rules are less relevant. This effect did not appear in melody
prediction, where repetition is more important.

###  7.4 Extrapolation and inductive bias

The results in this study confirm that an inductive bias is needed for
extrapolation, in the terminology of [28], in order to generalise in some
sense outside the space covered by the training data. This general challenge
has recently attracted some attention. E.g., [45] provided several solutions
to the related problem of learning equality of numbers (in binary
representation), which does not generalise from even to odd numbers as pointed
out already by [46]. As the authors point out in [45], an essential question
is which biases are relevant to the domain and problem. The identity problem
addressed here is in itself fundamental to learning about relations [47], as
relations depend on object identity. This further raises the question what is
needed to enable more complex concepts and rules to be learnt, such as more
general logical concepts and rules.

The identity rules also point to the lower-level problem that the natural
relations of position and belonging to objects are not naturally addressed in
neural networks. Other tasks may require different structures, relating for
example to arithmetics, geometry or physics [48]. We therefore see as an
important task the definition or predefined structures in neural networks, so
that they create useful inductive bias, but do not prevent learning of
functions that do not conform to that bias.

##  8 Conclusions

Our experiments show that the observation by [1], that neural networks are
unable to learn general identity rules, holds for standard feed-forward
networks, recurrent neural networks, and networks of GRUs and LSTMs. The
solution we propose here, the Relation Based Patterns (RBP), introduce an
additional structure with fixed weights into the network. Our experiments
confirm that the RBP structures enable the learning of abstract patterns based
on identity rules in classification and prediction as well as in mixed
abstract and concrete patterns. We have further found that adding RBP
structures improves performance in language and music prediction tasks.

Overall, we find that standard neural networks do not learn identity rules and
that adding RBP structure creates an inductive bias which enables this
extrapolation beyond training data with neural networks. This outcome raises
the question on how to develop further inductive biases for neural networks to
improve generalisation of learning on other tasks and more generally.

## References

  * [1] G. F. Marcus, S. Vijayan, S. Rao, P. Vishton, Rule learning by seven-month-old infants, Science, 283 283 (5398) (1999) 77–80.
  * [2] P. C. Gordon, K. J. Holyoak, Implicit learning and generalization of the mere exposure effect., Journal of Personality and Social Psychology, 45, 492–500.
  * [3] B. J. Knowlton, L. R. Squire, The information acquired during artificial grammar learning., Journal of Experimental Psychology: Learning, Memory, and Cognition, 20, 79 –91.
  * [4] B. J. Knowlton, L. R. Squire, Artificial grammar learning depends on implicit acquisition of both abstract and exemplar-specific information, Journal of Experimental Psychology: Learning, Memory, and Cognition, 22, 169 –181.
  * [5] M. Seidenberg, J. Elman, Do infants learn grammar with algebra or statistics?, Science 284 (5413) (1999) 433–433.
  * [6] J. Elman, Generalization, rules, and neural networks: A simulation of Marcus et. al, https://crl.ucsd.edu/~elman/Papers/MVRVsimulation.html.
  * [7] M. Vilcu, R. F. Hadley, Generalization in simple recurrent netrworks, in: Proceedings of the Annual Meeting of the Cognitive Science Society, Vol. 23, 2001, pp. 1072–1077.
  * [8] T. R. Shultz, A. C. Bale, Neural network simulation of infant familiarization to artificial sentences: Rule-like behavior without explicit rules and variables, Infancy, 2:4, 501-536, DOI: 10.1207/S15327078IN020407.
  * [9] G. Altmann, Z. Dienes, Rule learning by seven-month-old infants and neural networks, In Science 284 (5416) (1999) 875–875.
  * [10] M. Vilcu, R. F. Hadley, Two apparent ‘counterexamples’ to marcus: A closer look, Minds and Machines 15 (3-4) (2005) 359–382.
  * [11] T. R. Shultz, J.-P. Thivierge, D. Titone, Generalization in a model of infant sensitivity to syntactic variation, in: Proceedings of the Annual Meeting of the Cognitive Science Society, 2005, pp. 2009–20014.
  * [12] L. Shastri, S. Chang, A spatiotemporal connectionist model of algebraic rule-learning, Tech. Rep. TR-99-011, Berkeley, California: International Computer Science Institute (1999).
  * [13] M. Gasser, E. Colunga, Babies, variables, and connectionist networks, in: Proceedings of the 21st Annual Conference of the Cognitive Science Society, Lawrence Erlbaum, 1999, p. 794.
  * [14] P. F. Dominey, F. Ramus, Neural network processing of natural language: I. sensitivity to serial, temporal and abstract structure of language in the infant, Language and Cognitive Processes 15 (1) (2000) 87–127.
  * [15] M. H. Christiansen, C. M. Conway, S. Curtin, A connectionist single-mechanism account of rule-like behavior in infancy, in: Proceedings of the 22nd annual conference of the cognitive science society, 2000, pp. 83–88.
  * [16] R. G. Alhama, W. Zuidema, Pre-wiring and pre-training: What does a neural network need to learn truly general identity rules, CoCo at NIPS.
  * [17] J. A. Fodor, Z. W. Pylyshyn, Connectionism and cognitive architecture: A critical analysis, Cognition 28 (1-2) (1988) 3–71.
  * [18] R. F. Hadley, Systematicity in connectionist language learning, Mind & Language 9 (3) (1994) 247–272.
  * [19] P. Smolensky, The constituent structure of connectionist mental states: A reply to fodor and pylyshyn, Southern Journal of Philosophy 26 (Supplement) (1987) 137–161.
  * [20] J. Fodor, B. P. McLaughlin, Connectionism and the problem of systematicity: Why smolensky’s solution doesn’t work, Cognition 35 (2) (1990) 183–204.
  * [21] D. Chalmers, Why fodor and pylyshyn were wrong: The simplest refutation, in: Proceedings of the Twelfth Annual Conference of the Cognitive Science Society, Cambridge, Mass, 1990, pp. 340–347.
  * [22] L. Niklasson, T. van Gelder, Systematicity and connectionist language learning, Mind and Language 9 (3) (1994) 28–302.
  * [23] M. H. Christiansen, N. Chater, Generalization and connectionist language learning, Mind & Language 9 (3) (1994) 273–287.
  * [24] R. F. Hadley, Systematicity revisited: reply to christiansen and chater and niklasson and van gelder, Mind & Language 9 (4) (1994) 431–444.
  * [25] S. L. Frank, Getting real about systematicity, in: P. Calvo, J. Symons (Eds.), The architecture of cognition: Rethinking Fodor and Pylyshyn’s systematicity challenge, MIT Press, 2014, pp. 147–164.
  * [26] B. Lake, M. Baroni, Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks, in: International Conference on Machine Learning, 2018, pp. 2879–2888.
  * [27] I. Sutskever, O. Vinyals, Q. V. Le, Sequence to sequence learning with neural networks, in: Advances in neural information processing systems, 2014, pp. 3104–3112.
  * [28] G. F. Marcus, Deep learning : a critical appraisal, arXiv:1801.00631.
  * [29] S. Sabour, N. Frosst, G. E. Hinton, Dynamic routing between capsules, in: Advances in Neural Information Processing Systems, 2017, pp. 3856–3866.
  * [30] K. Kansky, T. Silver, D. A. Mély, M. Eldawy, M. Lázaro-Gredilla, X. Lou, N. Dorfman, S. Sidor, S. Phoenix, D. George, Schema networks: Zero-shot transfer with a generative causal model of intuitive physics, arXiv preprint arXiv:1706.04317.
  * [31] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. J. Goodfellow, R. Fergus, Intriguing properties of neural networks, CoRR abs/1312.6199.  arXiv:1312.6199.
URL http://arxiv.org/abs/1312.6199

  * [32] R. Feinman, B. M. Lake, Learning inductive biases with simple neural networks (2018).  arXiv:1802.02745.
  * [33] D. G. T. Barrett, F. Hill, A. Santoro, A. S. Morcos, T. Lillicrap, Measuring abstract reasoning in neural networks (2018).  arXiv:1807.04225.
  * [34] Y. Bengio, A. Courville, P. Vincent, Representation learning: A review and new perspectives, IEEE transactions on pattern analysis and machine intelligence 35 (8) (2013) 1798–1828.
  * [35] D. E. Rumelhart, G. E. Hinton, R. J. Williams, Learning internal representations by error propagation, Tech. rep., California Univ San Diego La Jolla Inst for Cognitive Science (1985).
  * [36] J. L. Elman, Finding structure in time, Cognitive science 14 (2) (1990) 179–211.
  * [37] K. Cho, B. Van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, Y. Bengio, Learning phrase representations using rnn encoder-decoder for statistical machine translation, arXiv preprint arXiv:1406.1078.
  * [38] S. Hochreiter, J. Schmidhuber, Long short-term memory, Neural Computation 9 (8) (1997) 1735–1780.  doi:10.1162/neco.1997.9.8.1735.
URL https://doi.org/10.1162/neco.1997.9.8.1735

  * [39] D. P. Kingma, J. Ba, Adam: A method for stochastic optimization, arXiv:1412.6980.
  * [40] M. Leshno, V. Y. Lin, A. Pinkus, S. Schocken, Multilayer feedforward networks with a nonpolynomial activation function can approximate any function, Neural networks 6 (6) (1993) 861–867.
  * [41] H. Siegelmann, E. Sontag, On the computational power of neural nets, Journal of Computer and System Sciences (1995) Volume 50, Issue 1, pp. 132–150.
  * [42] R. M. Kopparti, T. Weyde, Evaluating repetition based melody prediction over different context lengths, ICML Joint Workshop on Machine Learning and Music, Stockholm, Sweden, July 14.
  * [43] H. Schaffrath, The essen folksong collection in the humdrum kern formatDatabase edited by David Huron, CCAHR, Menlo Park, CA.
URL http://kern.ccarh.org/cgi-bin/ksbrow

  * [44] J. Langhabel, R. Lieck, M. Rohrmeier, Feature discovery for sequential prediction of monophonic music, International Society for Music Information Retrieval Conference (2017) 649–655.
  * [45] J. Mitchell, P. Minervini, P. Stenetorp, S. Riedel, Extrapolation in NLP, arXiv:1805.06648.
  * [46] G. F. Marcus, The algebraic mind: Integrating connectionism and cognitive science, Cambridge MIT Press.
  * [47] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, et al., Relational inductive biases, deep learning, and graph networks, arXiv preprint arXiv:1806.01261.
  * [48] N. Cohen, A. Shashua, Inductive bias of deep convolutional networks through pooling geometry (2016).  arXiv:1605.06743.


# Signatures of bath-induced quantum avalanches in a many-body–localized
system

Julian Léonard1,∗,† Sooshin Kim1,† Matthew Rispoli1 Alexander Lukin1 Robert
Schittko1 Joyce Kwan1 Eugene Demler2 Dries Sels3,4 Markus Greiner1,‡

###### Abstract

Strongly correlated systems can exhibit surprising phenomena when brought in a
state far from equilibrium. A spectacular example are quantum avalanches, that
have been predicted to run through a many-body–localized system and delocalize
it. Quantum avalanches occur when the system is locally coupled to a small
thermal inclusion that acts as a bath. Here we realize an interface between a
many-body–localized system and a thermal inclusion of variable size, and study
its dynamics. We find evidence for accelerated transport into the localized
region, signature of a quantum avalanche. By measuring the site-resolved
entropy we monitor how the avalanche travels through the localized system and
thermalizes it site by site. Furthermore, we isolate the bath-induced dynamics
by evaluating multipoint correlations between the bath and the system. Our
results have fundamental implications on the robustness of many-body–localized
systems and their critical behavior.

One of the founding principles of statistical physics is that a generic
macroscopic system can equilibrate on its own. This means that local
fluctuations of energy, magnetization, or particle density can relax towards
thermal equilibrium because interactions allow different parts of the system
to serve as reservoirs to each other. This universal picture has been
challenged by the idea of many-body localization (MBL), which suggests that
systems with strong disorder can evade thermalization even in the presence of
interactions Alet and Laflorencie (2018); Abanin  _et al._ (2019); Schreiber
_et al._ (2015); Smith  _et al._ (2016); Choi  _et al._ (2016); Rubio-Abadal
_et al._ (2019); Lukin  _et al._ (2019); Lüschen  _et al._ (2017); Rispoli
_et al._ (2019).

In one-dimensional systems, a stable MBL phase can be argued as follows:
Matrix elements of local operators decay exponentially with separation between
two points, whereas the density of states increases exponentially with the
system size. For strong disorder, matrix elements can thus be argued to decay
faster than the density of states increases, ultimately inhibiting relaxation.
However, the existence of MBL remains a subject of debate Abanin  _et al._ ;
Panda  _et al._ (2019); Sierant  _et al._ (2020); Šuntajs  _et al._ (2020a,
b); Luitz and Lev (2020); Kiefer-Emmanouilidis  _et al._ (2020a, b), since it
is unclear whether those conditions can actually be fulfilled. For instance,
by introducing a small region with weak disorder, part of the system may be
delocalized and thus give rise to local operators with non-exponential decay
Agarwal  _et al._ (2015); Bar Lev  _et al._ (2015); Žnidarič  _et al._ (2016);
Gopalakrishnan  _et al._ (2016); Agarwal  _et al._ (2017); Potter  _et al._
(2015); Vosk  _et al._ (2015); Gopalakrishnan  _et al._ (2015); Weiner  _et
al._ (2019); Khemani  _et al._ (2017a, b); Weiner  _et al._ (2019). Those
weakly disordered regions occur naturally in randomly disordered systems, when
potential offsets on consecutive lattice sites accidentally coincide Griffiths
(1969); McCoy (1969). The dynamics in MBL systems in the presence of a locally
thermalizing region have been predicted to occur in so-called quantum
avalanches, which imply those small islands grow by absorbing nearby
disordered regions Nandkishore and Gopalakrishnan (2017); De Roeck and
Huveneers (2017); Luitz  _et al._ (2017); Thiery  _et al._ (2018); Crowley and
Chandran (2020). Under which conditions quantum avalanches can arise, run out
of steam, or propagate without halt determines the ultimate fate of MBL at
very long times. Their understanding is thus closely connected to discerning
thermalization in interacting many-body systems.

Figure 1: Bath-induced quantum avalanches. a, Two scenarios at an interface of
a thermal bath (clean) and a localized (disordered) region: a weak bath
penetrates logarithmically slow and localization remains robust (left), or an
avalanche from a strong bath thermalizes the disordered region site by site
(right). b, Fluorescence pictures of a two-dimensional Mott insulator at unity
filling, and of the initialized one-dimensional system of $L$ sites. Projected
optical potentials isolate the system and apply site-resolved offsets onto the
disordered region (blue). c, The initial state is brought far from equilibrium
through a quantum quench by abruptly enabling tunneling along all links, then
evolved under the Hamiltonian, until we detect the site-resolved atom number
with a fluorescence picture. d, The system’s dynamics are governed by the
Bose-Hubbard model with tunneling energy $J$ and on-site interaction energy
$U$, extended by a disorder potential with amplitude $W$ in the disordered
region. Figure 2: Accelerated transport across the clean-disorder interface.
a, Density correlations for all pairs of sites in a system consisting of
$L_{\text{clean}}=L_{\text{dis}}=6$ at disorder strength $W=9.1\,J$. After a
quantum quench, an uncorrelated initial state (left) develops separate
dynamics within each subsystem (center), followed by particle transport across
the clean-disorder interface (grey dashed lines) for evolution times $\gg
L_{\text{clean}},L_{\text{dis}}$ (right). Cuts show the total density
correlations $g^{(2)}(i)$ of the clean region with site $i$ (i.e. average of
top six rows, excluding diagonal entries), featuring homogeneous coupling
among the clean sites, and exponentially decaying anti-correlations with the
distance of the disordered site from the interface. b, The decay length
$\xi_{\text{d}}$ of the total density correlations increases first
logarithmically in time and accelerates at long evolution times. c, The decay
length $\xi_{\text{d}}$ after an evolution time of $100\tau$ grows with
$L_{\text{clean}}$, indicating improved particle transport into the disordered
region. The data point at $L_{\text{clean}}=0$ and the dashed line show the
localization length of an isolated MBL system. Solid lines (bars in panel c)
show the prediction from exact numerics without free parameters. Error bars
denote the s.e.m. (below the marker size in panel a).

Bath-induced relaxation dynamics can often be captured semi-classically in the
context of Fermi’s golden rule. In an isolated MBL system particle
rearrangements are restricted to the length scales of the order of the
localization length $\xi_{\text{loc}}$. The relaxation rate $\Gamma_{i}$ of a
lattice site at distance $i$ coupled to the bath is captured by Fermi’s golden
rule $\Gamma_{i}=g_{i}^{2}\rho_{\text{bath}}$. Here, the coupling for a
relaxation process on site $i$ away from the bath leading to a transfer of
energy or particles into the bath is set by $g_{i}\propto
Je^{-i/\xi_{\text{loc}}}$. The density of states in the thermal region is
exponential in its size, i.e. $\rho_{\text{bath}}\propto J^{-1}e^{\alpha
L_{\text{bath}}}$ with a constant $\alpha$. This model implies that site $i$
shows relaxation after a time $T_{i}=1/\Gamma_{i}$, or equivalently, after an
evolution time $T$ we expect relaxation on the sites up to the distance
$d_{\text{FGR}}(T)\sim\xi_{\text{loc}}\log(J^{2}\rho_{\text{bath}}T)$. In
conclusion, within a perturbative description MBL remains robust against a
local bath, with a bath penetration into the MBL region that increases only
logarithmically in time. Quantum avalanches, however, are predicted to emerge
from dynamics beyond Fermi’s golden rule. As the bath begins to delocalize
neighboring disordered sites, the size of the thermalizing bath expands,
leading to an increase in its density of states.

In this work we explore the dynamics of an MBL system coupled to a thermal
bath (Fig. 1). We observe phenomena that suggest the presence of non-
perturbative avalanche processes, while other features of dynamics can be
explained using the perturbative Fermi’s golden rule. Our experimental
protocol starts by preparing a Mott-insulating state with one 87Rb atom on
each site of a two-dimensional optical lattice (Fig. 1b). The system is placed
in the focus of a high-resolution imaging system through which we project
site-resolved repulsive potentials on individual lattice sites. We isolate a
one-dimensional system of $L$ lattice sites from the Mott insulator and add
potential offsets to the lattice sites. At this point, the system remains in a
product state of one atom per lattice site. We then perform a quantum quench
by abruptly reducing the lattice depth (Fig. 1c). The subsequent non-
equilibrium dynamics are described by the Bose-Hubbard Hamiltonian:

$\displaystyle\hat{\mathcal{H}}$
$\displaystyle=-J\sum_{i}\left(\hat{a}_{i}^{\dagger}\hat{a}_{i+1}+h.c.\right)$
$\displaystyle+\frac{U}{2}\sum_{i}\hat{n}_{i}\left(\hat{n}_{i}-1\right)+W\sum_{i\in
L_{\text{dis}}}h_{i}\hat{n}_{i}\text{,}$

where $\hat{a}^{\dagger}_{i}$ ($\hat{a}_{i}$) is the creation (annihilation)
operator for a boson on site $i$, and
$\hat{n}_{i}=\hat{a}^{\dagger}_{i}\hat{a}_{i}$ is the particle number
operator. The first term describes the tunneling between all neighboring
lattice sites, and the second term represents the on-site repulsive
interactions. The last term introduces a site-resolved energy offset. We set
$h_{i}=0$ for all lattice sites in the clean region of size
$L_{\text{clean}}$, whereas the energy offsets in the disordered region of
size $L_{\text{dis}}$ follow a quasi-periodic disorder distribution
$h_{i}=\cos(2\pi\beta i+\phi)$ with $1/\beta\approx 1.618$, phase $\phi$ and
amplitude $W$. The quasi-periodic distribution avoids nearby lattice sites to
coincidentally have similar energy offsets, which inhibits the presence of
secondary rare regions within the disordered region Setiawan  _et al._ (2017).
After a variable evolution time, we read out the site-resolved atom number by
fluorescence imaging. The applied unitary evolution preserves the initial
purity of $99.1(2)\%$ per site Kaufman  _et al._ (2016); Lukin  _et al._
(2019). All observables are disorder-averaged by realizing potential with
different $\phi$. The tunneling time $\tau=\hbar/J=4.3(1)\,\text{ms}$ (with
the reduced Planck constant $\hbar$), the interaction strength $U=2.87(3)\,J$,
and the number of disordered sites $L_{\text{dis}}=6$ remain constant in all
experiments.

We first use the full site-resolved readout of our microscope to investigate
the local transport dynamics in the system. The connected density-density
correlations
$\langle\hat{n}_{i}\hat{n}_{j}\rangle_{c}=\langle\hat{n}_{i}\hat{n}_{j}\rangle-\langle\hat{n}_{i}\rangle\langle\hat{n}_{j}\rangle$
detects correlations between the particle numbers on site $i$ and $j$ Rispoli
_et al._ (2019). Negative values of $\langle\hat{n}_{i}\hat{n}_{j}\rangle_{c}$
signal anti-correlated density fluctuations, and thus particles motion between
the involved sites (Fig. 2a). In the following, we consider a system with
$L_{\text{clean}}=6$ at disorder strength $W=9.1\,J$ after different evolution
times $T$ after the quantum quench. At the beginning of the evolution
($T=0\tau$), we do not detect any correlations, because the initial state is a
product state. After short evolution times ($T\lesssim\tau L$), we observe the
buildup of spatially dependent anti-correlations in the system. Within the
clean region all lattice sites develop mutual anti-correlations, signaling
delocalizing particles. In contrast, the anti-correlations in the disordered
region remain short-ranged, indicating localized particles. At this time, we
do not detect significant anti-correlations between the clean and the
disordered region.

The situation changes for long evolution times ($T\gg\tau L$), where the
correlations in the clean region have spread out evenly among all pairs of
lattice sites, signaling homogeneously delocalized particles. Furthermore, we
observe the buildup of anti-correlations between lattice sites in the clean
and the disordered region, evidence for transport dynamics across the
interface. Each of the disordered sites is equally anti-correlated to all
clean sites, which suggests that the clean region acts as a homogeneous bath
for the disordered region. Motivated by this picture, we extract the total
correlations of the clean region $g^{(2)}(i)=\sum_{j\in
L_{\text{clean}}}\langle\hat{n}_{i}\hat{n}_{j}\rangle_{\text{c}}$ by taking
the sum of the correlations of each site with all clean sites (Fig. 2b cute).
The results show a decay with distance from the clean region, in agreement
with the Fermi golden rule picture of exponentially decaying couplings between
bath and MBL.

While a static bath spectrum causes bath correlations to penetrate MBL
logarithmically in time, a signature of the quantum avalanche is an
accelerated increase, faster than logarithmically in time. In order to test
this picture, we quantify the correlation decay into the disordered region by
measuring the average distance $\xi_{\text{d}}=\sum_{i\in
L_{\text{dis}}}ig^{(2)}(i)$ from the clean region over which anti-correlations
form (Fig. 2b). At short times the decay length $\xi_{\text{d}}$ increases
logarithmically in time, but accelerates at long evolution times — signature
for the emergence of a quantum avalanche.

Figure 3: Site-resolved thermalization dynamics. a, The atom number
probability distribution for the edge sites in the clean region (left) and the
disordered region (right), measured after $100\tau$ in a system consisting of
$L_{\text{clean}}=L_{\text{dis}}=6$ at disorder strength $W=9.1\,J$. b, Local
entropy per particle $s_{i}=-\sum_{n}p_{n}\log
p_{n}/\langle\hat{n}_{i}\rangle$ extracted from the atom number distribution
on site $i$. The entropy grows after a stationary evolution whose length
depends on the distance from the interface (indicated by the grey dashed
line). Traces are vertically offset for better readability. c, Local entropy
$s_{i}$ (offset by $s_{i}(T=1\tau)$) for all disordered sites. Solid lines
(bars in panel a) show the prediction from exact numerics without free
parameters. Error bars denote the s.e.m. (below the marker size in panel a).
Figure 4: Bath-induced many-body correlations. a, Three-point correlations
$\langle\hat{n}_{i}\hat{n}_{j}\hat{n}_{k}\rangle_{c}$ among pairs of clean
sites $i$, $j$ and one disordered site $k$ (summed over all disordered $k$) in
a system with $L_{\text{clean}}=L_{\text{dis}}=6$ at disorder strength
$W=9.1\,J$ and evolution time $T=100(1)$. Cuts across the site $j=6$ (arrows)
show nonzero entries for all sites, evidence for multi-particle entanglement
between all sites in the clean region with the disordered sites. The flat
distribution visualizes the homogeneous coupling to the disordered region. b,
Correlations $\langle\hat{n}_{i}\hat{n}_{j}\hat{n}_{k}\rangle_{c}$ among pairs
of disordered sites $i$, $j$ and one clean site $k$ (summed over all clean
$k$) vary strongly with the chosen lattice sites, and decrease with the
distance from the clean region. The presence of multi-point correlations
demonstrates non-perturbative dynamics: delocalization is driven through many-
body processes between the disordered region and the clean region. c, We
average over all off-diagonal sites and find a maximum for intermediate
disorder for the MBL-bath entanglement. d, The total multi-point correlations
among disordered sites with the bath show a similar maximum at slightly lower
intermediate disorder. Solid lines show the prediction from exact numerics
without free parameters. Error bars denote the s.e.m.

The size $L_{\text{clean}}$ determines the number of degrees of freedom of the
initial thermal region, and thus the spectral density of the thermal bath.
While a bath of small number of degrees of freedom can only couple to
disordered sites at distances on the order of the localization length
$\xi_{\text{loc}}$, larger baths are expected to significantly exceed this
length scale. The perturbative picture predicts that
$\xi_{\text{d}}\propto\xi_{\text{loc}}\log(J\rho_{\text{bath}})\propto\xi_{\text{loc}}\times
L_{\text{clean}}$, therefore a deviation from this proportionality can be
regarded as evidence for non-perturbative dynamics in form of avalanches. In
order to investigate this effect, we realize systems with different
$L_{\text{clean}}$, while keeping $L_{\text{dis}}=6$ constant (Fig. 2c). For
each system size, we characterize the particle transport by measuring
$\xi_{\text{d}}$ after an evolution time of $100(1)\tau$. Our results show an
increasing value of $\xi_{\text{d}}$ for larger $L_{\text{clean}}$. The
enhanced $\xi_{\text{d}}$ for $L_{\text{clean}}=6$ suggests the presence of a
quantum avalanche in the system.

We next examine the local thermalization dynamics in a system with
$L_{\text{clean}}=L_{\text{dis}}=6$. The site-resolved full atom number
readout enables us to measure the atom number distribution on a local level
(Fig. 3a). Lattice sites in the clean region show a distribution corresponding
to a thermal ensemble, whereas lattice sites in the disordered region show a
distribution with enhanced probability for one particle, the initial state of
the system. We quantify the site-resolved thermalization dynamics with the
entropy per particle $s_{i}=-\sum_{n_{i}}{p(n_{i})}\log
p(n_{i})/\langle\hat{n}_{i}\rangle$ on site $i$ from the atom number
distributions. We observe reduced thermalization dynamics of the disordered
sites with increasing distance from the interface (Fig. 3b). Moreover, the
data suggest that the dynamics are first stationary until thermalization sets
in with a delay that is exponential in the site’s distance from the interface.
This picture is confirmed by our exact numerical calculations.

The signatures for quantum avalanches imply that many-body processes drive the
long-term dynamics of the system. We investigate this effect through
multipoint correlations Kubo (1962); Rispoli  _et al._ (2019). The presence of
non-zero three-point connected correlations
$\langle\hat{n}_{i}\hat{n}_{j}\hat{n}_{k}\rangle_{c}$ signals the presence of
entanglement among all involved lattice sites, which cannot be explained by
lower order processes. We start by evaluating the connected correlations
$\langle\hat{n}_{i}\hat{n}_{j}\hat{n}_{\text{dis}}\rangle_{c}$ among two clean
lattice sites $i$, $j$ and a disordered site $k$, summed over all possible $k$
(Fig. 4a). The correlations are non-zero across the clean region, and their
homogeneous distribution indicates that all clean sites contribute equally to
the delocalization in the disordered region. In contrast, when evaluating the
connected correlations
$\langle\hat{n}_{i}\hat{n}_{j}\hat{n}_{\text{clean}}\rangle_{c}$ among two
disordered sites $i$, $j$ and a clean site $k$, averaged over all possible $k$
(Fig. 4b), the data show a strong dependence on the involved disordered sites.
Close to the interface we find strong correlations, whereas they are absent
for distant sites. We quantify the presence of many-body correlations at
different disorder strengths and find a maximum at intermediate strengths
(Fig. 4c,d), close to the estimated critical point of the system Rispoli  _et
al._ (2019).

In conclusion, we experimentally studied signatures of quantum avalanches in
an MBL system, set in motion by a thermal inclusion. We observed an
accelerated intrusion of the bath in the MBL system, its evolution to thermal
equilibrium site after site, and the many-body entanglement between the two
subsystems. By varying the size $L_{\text{clean}}$, we studied the emergence
of quantum avalanches for increased number of degrees of freedom of the bath.
In future, our experiments can be readily extended in many ways. For example,
one could more systematically study the fate of quantum avalanches as a
function of bath size and localization length. By increasing both the system
size of the disordered region, one could explore the interplay at intermediate
disorder strengths in a quantitive way through its scaling behaviour, i.e. by
increasing the system size at constant ratio of $L_{\text{clean}}$ and
$L_{\text{dis}}$, which may provide insight into the critical behaviour of the
transition. An interesting extension would also be the influence of the
statistical distribution of the disorder on the critical behaviour of the
system.

We acknowledge fruitful discussions with K. Agarwal, V. Khemani, M. Knap, M.
Lebrat and J. Marino. We are supported by grants from the National Science
Foundation, the Gordon and Betty Moore Foundations EPiQS Initiative, an Air
Force Office of Scientific Research MURI program, an Army Research Office MURI
program, the Swiss National Science Foundation (J. L.), and the NSF Graduate
Research Fellowship Program (S. K.).

∗ current address: Vienna Center for Quantum Science and Technology,
Atominstitut, TU Wien, Vienna, Austria; † These authors contributed equally to
this work; $\ddagger$ email<EMAIL_ADDRESS>
## References

  * Alet and Laflorencie (2018) F. Alet and N. Laflorencie, Comptes Rendus Physique 19, 498 (2018), arXiv:1711.03145 .
  * Abanin  _et al._ (2019) D. A. Abanin, E. Altman, I. Bloch, and M. Serbyn, Reviews of Modern Physics 91, 21001 (2019).
  * Schreiber  _et al._ (2015) M. Schreiber, S. S. Hodgman, P. Bordia, H. P. Lüschen, M. H. Fischer, R. Vosk, E. Altman, U. Schneider, and I. Bloch, Science 349, 842 (2015).
  * Smith  _et al._ (2016) J. Smith, A. Lee, P. Richerme, B. Neyenhuis, P. W. Hess, P. Hauke, M. Heyl, D. A. Huse, and C. Monroe, Nat. Phys. 12, 907 (2016).
  * Choi  _et al._ (2016) J.-y. Choi, S. Hild, J. Zeiher, P. Schauß, A. Rubio-abadal, T. Yefsah, V. Khemani, D. A. Huse, I. Bloch, and C. Gross, Science 352, 1547 (2016).
  * Rubio-Abadal  _et al._ (2019) A. Rubio-Abadal, J. Y. Choi, J. Zeiher, S. Hollerith, J. Rui, I. Bloch, and C. Gross, Physical Review X 9, 41014 (2019), arXiv:1805.00056 .
  * Lukin  _et al._ (2019) A. Lukin, M. Rispoli, R. Schittko, M. E. Tai, A. M. Kaufman, S. Choi, V. Khemani, J. Léonard, and M. Greiner, Science 260, 256 (2019).
  * Lüschen  _et al._ (2017) H. P. Lüschen, P. Bordia, S. Scherg, F. Alet, E. Altman, U. Schneider, and I. Bloch, Physical Review Letters 119, 260401 (2017).
  * Rispoli  _et al._ (2019) M. Rispoli, A. Lukin, R. Schittko, S. Kim, M. E. Tai, J. Léonard, and M. Greiner, Nature 573, 385 (2019), arXiv:1812.06959 .
  * (10) D. A. Abanin, J. H. Bardarson, G. de Tomasi, S. Gopalakrishnan, V. Khemani, S. A. Parameswaran, F. Pollmann, A. C. Potter, M. Serbyn, and R. Vasseur, arXiv , 1arXiv:1911.04501 .
  * Panda  _et al._ (2019) R. K. Panda, A. Scardicchio, M. Schulz, S. R. Taylor, and M. Žnidarič, Europhys. Lett. 128 (2019), 10.1209/0295-5075/128/67003, arXiv:1911.07882 .
  * Sierant  _et al._ (2020) P. Sierant, D. Delande, and J. Zakrzewski, Physical Review Letters 124, 186601 (2020), arXiv:1911.06221 .
  * Šuntajs  _et al._ (2020a) J. Šuntajs, J. Bonča, T. Prosen, and L. Vidmar, Physical Review B 102, 1 (2020a), arXiv:2004.01719 .
  * Šuntajs  _et al._ (2020b) J. Šuntajs, J. Bonca, T. Prosen, and L. Vidmar, Phys. Rev. E 102, 062144 (2020b).
  * Luitz and Lev (2020) D. J. Luitz and Y. B. Lev, arXiv 102, 100202 (2020), arXiv:2007.13767 .
  * Kiefer-Emmanouilidis  _et al._ (2020a) M. Kiefer-Emmanouilidis, R. Unanyan, M. Fleischhauer, and J. Sirker, Physical Review Letters 124, 243601 (2020a), arXiv:2003.04849 .
  * Kiefer-Emmanouilidis  _et al._ (2020b) M. Kiefer-Emmanouilidis, R. Unanyan, M. Fleischhauer, and J. Sirker, arXiv (2020b), arXiv:2010.00565 .
  * Agarwal  _et al._ (2015) K. Agarwal, S. Gopalakrishnan, M. Knap, M. Müller, and E. Demler, Physical Review Letters 114, 1 (2015), arXiv:1408.3413 .
  * Bar Lev  _et al._ (2015) Y. Bar Lev, G. Cohen, and D. R. Reichman, Physical Review Letters 114, 1 (2015), arXiv:1407.7535 .
  * Žnidarič  _et al._ (2016) M. Žnidarič, A. Scardicchio, and V. K. Varma, Physical Review Letters 117, 1 (2016), arXiv:1604.08567 .
  * Gopalakrishnan  _et al._ (2016) S. Gopalakrishnan, K. Agarwal, E. A. Demler, D. A. Huse, and M. Knap,  134206, 1 (2016).
  * Agarwal  _et al._ (2017) K. Agarwal, E. Altman, E. Demler, S. Gopalakrishnan, D. A. Huse, and M. Knap, Annalen der Physik 529, 1 (2017), arXiv:1611.00770 .
  * Potter  _et al._ (2015) A. C. Potter, R. Vasseur, and S. A. Parameswaran, Physical Review X 5, 031033 (2015).
  * Vosk  _et al._ (2015) R. Vosk, D. A. Huse, and E. Altman, Physical Review X 5, 1 (2015), arXiv:1412.3117 .
  * Gopalakrishnan  _et al._ (2015) S. Gopalakrishnan, M. Müller, V. Khemani, M. Knap, E. Demler, and D. A. Huse, Physical Review B - Condensed Matter and Materials Physics 92, 1 (2015), arXiv:1502.07712 .
  * Weiner  _et al._ (2019) F. Weiner, F. Evers, and S. Bera, Physical Review B 100, 1 (2019), arXiv:1904.06928 .
  * Khemani  _et al._ (2017a) V. Khemani, S. P. Lim, D. N. Sheng, and D. A. Huse, Physical Review X 7, 021013 (2017a).
  * Khemani  _et al._ (2017b) V. Khemani, D. N. Sheng, and D. A. Huse,  075702, 1 (2017b).
  * Griffiths (1969) R. B. Griffiths, Phys. Rev. Lett. 23, 17 (1969).
  * McCoy (1969) B. M. McCoy, Physical Review Letters 23, 383 (1969).
  * Nandkishore and Gopalakrishnan (2017) R. Nandkishore and S. Gopalakrishnan, Ann. Phys. (Berlin) 529, 1600181 (2017).
  * De Roeck and Huveneers (2017) W. De Roeck and F. Huveneers, Physical Review B 95, 1 (2017), arXiv:1608.01815 .
  * Luitz  _et al._ (2017) D. J. Luitz, F. Huveneers, and W. De Roeck, Physical Review Letters 119, 150602 (2017).
  * Thiery  _et al._ (2018) T. Thiery, F. Huveneers, M. Müller, and W. De Roeck, Physical Review Letters 121, 1 (2018), arXiv:1706.09338 .
  * Crowley and Chandran (2020) P. J. Crowley and A. Chandran, Physical Review Research 2, 033262 (2020), arXiv:1910.10812 .
  * Setiawan  _et al._ (2017) F. Setiawan, D. L. Deng, and J. H. Pixley, Physical Review B 96, 1 (2017), arXiv:1707.02984 .
  * Kaufman  _et al._ (2016) A. M. Kaufman, M. E. Tai, A. Lukin, M. Rispoli, R. Schittko, P. M. Preiss, and M. Greiner, Science 353, 794 (2016).
  * Kubo (1962) R. Kubo, J. Phys. Soc. Jpn. 17, 1100 (1962).
  * Zupancic  _et al._ (2016) P. Zupancic, P. M. Preiss, R. Ma, M. E. Tai, M. Rispoli, and R. Islam, Optics Express 24, 13881 (2016).
  * Sidje (1998) R. B. Sidje, ACM Trans. Math. Softw. 24, 130 (1998).

##  I Supplementary information

###  I.1 Experimental sequence

Mott insulator preparation. All described experiments start with a Bose-
Einstein condensate of bosonic 87Rb atoms in the $|F=1,m_{F}=-1\rangle$
hyperfine state. This ultracold gas is loaded into a single 2D plane of a deep
lattice along the vertical direction with lattice constant $1.5\mu m$ at laser
wavelength $760\,\text{nm}$. This lattice stays on for the remainder of the
experiment. We use an attractive dimple potential to isolate a controlled
number of atoms from the 2D gas and load them into the center of a repulsive
ring-shaped potential, created from a second laser beam at wavelength
$760\,\text{nm}$. At this point the atoms form a two-dimensional superfluid
with harmonic in-plane confinement. We then ramp up further laser beams at
wavelength $760\,\text{nm}$ over $250\,\text{ms}$ to create a repulsive two-
dimensional square lattice with lattice constant $a=680\,\text{nm}$ in both
directions and lattice depth $45E_{\text{r}}$, where
$E_{\text{r}}=h^{2}/(2ma^{2})=h\times 1.1\,\text{kHz}$ is the recoil energy of
a 87Rb atom of mass $m$.

Initial state preparation. We use two digital micro-mirror devices (DMD) to
project repulsive potentials onto the Mott insulator. The DMDs are placed in
the Fourier plane with respect to the atoms, which allows us to project
diffraction limited arbitrary potentials that correct for optical wavefront
aberrations in the imaging system Zupancic  _et al._ (2016). We optically
confine a single chain of $L=L_{\text{clean}}+L_{\text{dis}}$ lattice sites
within the Mott insulator’s unity-filling shell, and subsequently ramp down
the power of the optical lattice. We use a repulsive deconfining beam to eject
all atoms outside the confinement potential, while each atom within the
projected confinement potential remains pinned on its lattice site. We then
ramp the lattice back to $45E_{\text{r}}$ and remove the confining DMD
potential. After post-selecting for the atom number $N=L$, this procedure
results in an initial state of $99.1(2)\,\%$ fidelity per site.

Quantum quench and state evolution. We use the first DMD to project a “wall-
potential” on the adjacent sites around the one-dimensional system, which
provides a box-like confinement. This potential is registered to the position
of the optical lattice and defines the size of the one-dimensional system. We
simultaneously use the second DMD to project a custom, quasi-periodic disorder
potential onto the disordered region of the system. The disorder strength $W$
is tuned by the intensity of the DMD potential. The quantum quench is
initiated by lowering the lattice depth along the one-dimensional system from
$45E_{\text{r}}$ to $8E_{\text{r}}$. After a variable evolution time we freeze
the dynamics by ramping the lattice back to $45E_{\text{r}}$.

Full quantum state read out. We first let the atom populations located on
individual lattice sites expand into independent tubes and use fluorescence
imaging with an optical molasses beam to perform a site-resolved atom number
measurement. The expansion step before the imaging procedure is employed to
avoid parity projection during the imaging process. We subsequently post-
select our data by excluding any images which do not contain the correct total
number of atoms. The error in postselection, that is the fraction of falsely
post-selected snapshots due to the finite readout fidelity, is $<0.1\,\%$ for
all the experiments, small compared to the statistical error in the data.

###  I.2 Calibration of Hamiltonian parameters

The calibration procedure for the Bose-Hubbard parameters is identical to the
one described in Lukin  _et al._ (2019). We obtain $J=h\times
37.5(1)\,\text{Hz}$ and $U=h\times 107(1)\,\text{Hz}$.

###  I.3 Multi-point correlations

Generically, a $n^{\mathrm{th}}$ order correlation function can be measured
from a set of operators $\mathcal{O}_{i}$ by their joint expectation value
$\langle\prod_{i=1}^{n}\mathcal{O}_{i}\rangle=\langle\mathcal{O}_{1}\mathcal{O}_{2}...\mathcal{O}_{n}\rangle$.
However, this joint expectation value captures two kinds of information:
“disconnected” correlations that exist at $n^{\mathrm{th}}$ order due to
existing lower order correlations, and “connected” correlations that only
exist at order $n$ and can’t be described by factorization into correlations
of lower order Kubo (1962).

In the two-point case, this would mean comparing the measured value of
$\langle\mathcal{O}_{i}\mathcal{O}_{j}\rangle$ to the product of their
individual expectation values
$\langle\mathcal{O}_{i}\rangle\langle\mathcal{O}_{j}\rangle$. The “connected”
part of the correlation between $i$ and $j$ is defined as the correlations
that remain after removing the contributions from factorization into smaller
groups. This motivates the definition of
$\langle\mathcal{O}_{i}\mathcal{O}_{j}\rangle_{\text{c}}=\langle\mathcal{O}_{i}\mathcal{O}_{j}\rangle-\langle\mathcal{O}_{i}\rangle\langle\mathcal{O}_{j}\rangle$.

For a three-point connected correlation function, we must subtract out
contributions that come from connected two-point correlations that can look
like three-point correlations when randomly combined with a residual 1-point
correlation. This is how the connected three-point correlation function is
defined in the main text for the on-site number operator $\hat{n}_{i}$.

$\displaystyle\langle\mathcal{O}_{i}\mathcal{O}_{j}\mathcal{O}_{k}\rangle_{\text{c}}=$
$\displaystyle{}\langle\mathcal{O}_{i}\mathcal{O}_{j}\mathcal{O}_{k}\rangle$
$\displaystyle-$
$\displaystyle{}G_{\text{c}}^{(2)}(i,j)\langle\mathcal{O}_{k}\rangle-
G_{\text{c}}^{(2)}(i,k)\langle\mathcal{O}_{j}\rangle-
G_{\text{c}}^{(2)}(j,k)\langle\mathcal{O}_{i}\rangle$ $\displaystyle-$
$\displaystyle{}\langle\mathcal{O}_{j}\rangle\langle\mathcal{O}_{j}\rangle\langle\mathcal{O}_{k}\rangle$

Higher order multi-point correlations can be constructed in a similar way
Rispoli  _et al._ (2019).

###  I.4 Numerical calculations

The experimental studied system sizes have Hilbert space dimensions of up to
$1.3\times 10^{6}$ ($L=12$, N=12). Due to the non-equilibrium evolution and
the disorder, matrix diagonalization for such systems is computationally
challenging. Instead, we implement an exact numerical integration of
Schrödinger’s equation $\ket{\psi(t)}=e^{-i\hat{H}t/\hbar}\ket{\psi_{0}}$
based on the Krylov-subspace method Sidje (1998). This method provides an
memory- and CPU-run-time efficient way to numerically compute the time
evolution while achieving high, controlled precision. All numerical
calculations are averaged over 200 different realizations of the quasi-
periodic potential. The computations are performed on the Harvard Odyssey
computing cluster (for specifications see:
https://www.rc.fas.harvard.edu/odyssey/).

###  I.5 Data Analysis

For all experiments we average over 197 patterns of quasi-periodic potentials,
each with a different phase $\phi$ of the quasi-periodic potential. The data
are taken from a running average over those patterns by randomly sampling a
given number of realizations and treating them as independent measurements of
the same system.

We extract the decay length $\xi_{d}$ by computing the first moment of the
non-local density-density correlations
$\xi_{d}=\sum_{i}i\langle\hat{n}_{i}\hat{n}_{j}\rangle_{c}$.

The single-site entropy in Fig. 3a is extracted from the edge sites. The edge
sites are most insensitive to the dynamics at the clean-disorder interface and
therefore allow for a fair indicator for thermalization Khemani  _et al._
(2017a).

Error bars are computed by resampling the set of snapshots with replacement
(bootstrapping).

The number of samples for each experiment is summarized in the following
table:

Figure |  Number of samples
---|---
2a,b |  199 ($0\tau$), 86 ($1\tau$), 242 ($3.1\tau$), 294 ($10\tau$), 315 ($31.9\tau$), 456 ($100\tau$)
2c |  456 ($L_{\text{clean}}=0$), 835 ($L_{\text{clean}}=2$), 134 ($L_{\text{clean}}=4$), 456 ($L_{\text{clean}}=6$)
3a |  835 ($100\tau$)
3b,c |  same samples as for Fig. 2a,b
4a,b |  456
4c,d |  85 ($W=2.9\,J$), 71 ($W=4.4\,J$), 553 ($W=5.5\,J$), 179 ($W=6.2\,J$), 198 ($W=7.0\,J$), 191 ($W=7.7\,J$), 200 ($W=8.4\,J$), 623 ($W=9.1\,J$), 237 ($W=9.6\,J$)