marginparsep has been altered.
topmargin has been altered.
marginparpush has been altered.
The page layout violates the ICML style. Please do not change the page layout,
or include packages like geometry, savetrees, or fullpage, which change it for
you. We’re not able to reliably undo arbitrary changes to the style. Please
remove the offending package(s), or layout-changing commands and try again.

Opening the AI black box:
program synthesis via mechanistic interpretability

Eric J. Michaud * 1 2  Isaac Liao * 1  Vedang Lad * 1  Ziming Liu * 1 2  Anish
Mudide 1  Chloe Loughridge 3  Zifan Carl Guo 1  Tara Rezaei Kheirkhah 1
Mateja Vukelić 1  Max Tegmark 1 2

††footnotetext: *Equal contribution, alphabetical order 1Massachusetts
Institute of Technology, Cambridge, MA, USA 2Institute for Artificial
Intelligence and Fundamental Interactions 3Harvard University, Cambridge, MA,
USA. Correspondence to: Max Tegmark<EMAIL_ADDRESS>
Preprint. Under review.

###### Abstract

We present MIPS, a novel method for program synthesis based on automated
mechanistic interpretability of neural networks trained to perform the desired
task, auto-distilling the learned algorithm into Python code. We test MIPS on
a benchmark of 62 algorithmic tasks that can be learned by an RNN and find it
highly complementary to GPT-4: MIPS solves 32 of them, including 13 that are
not solved by GPT-4 (which also solves 30). MIPS uses an integer autoencoder
to convert the RNN into a finite state machine, then applies Boolean or
integer symbolic regression to capture the learned algorithm. As opposed to
large language models, this program synthesis technique makes no use of (and
is therefore not limited by) human training data such as algorithms and code
from GitHub. We discuss opportunities and challenges for scaling up this
approach to make machine-learned models more interpretable and trustworthy.

##  1 Introduction

Machine-learned algorithms now outperform traditional human-discovered
algorithms on many tasks, from translation to general-purpose reasoning. These
learned algorithms tend to be black-box neural networks, and we typically lack
a full understanding of how they work. This has motivated the growing field of
mechanistic interpretability, aiming to assess and improve their
trustworthiness. Major progress has been made in interpreting and
understanding smaller models, but this work has involved human effort, which
raises questions about whether it can scale to larger models. This makes it
timely to investigate whether mechanistic interpretability can be fully
automated tegmark2023provably.

The goal of the present paper is to take a modest first step in this direction
by presenting and testing MIPS (Mechanistic-Interpretability-based Program
Synthesis), a fully automated method that can distill simple learned
algorithms from neural networks into Python code. The rest of this paper is
organized as follows. After reviewing prior work in Section II, we present our
method in Section III, test it on a benchmark in Section IV and summarize our
conclusions in Section V.

##  2 Related Work

Program synthesis is a venerable field dating back to Alonzo Church in 1957;
zhou2023survey and odena2020bustle provide recent reviews of the field. Large
language Models (LLMs) have become increasingly good at writing code based on
verbal problem descriptions or auto-complete. We instead study the common
alternative problem setting known as “programming by example” (PBE), where the
desired program is specified by giving examples of input-output pairs
wu2023programming. The aforementioned papers review a wide variety of program
synthesis methods, many of which involve some form of search over a space of
possible programs. LLMs that synthesize code directly have recently become
quite competitive with such search-based approaches sobania2022choose. Our
work provides an alternative search-free approach where the program learning
happens during neural network training rather than execution.

Our work builds on the recent progress in mechanistic interpretability (MI) of
neural networks (olah2020zoom; cammarata2020curve; wang2022interpretability;
olsson2022context). Much MI work has tried to understand how neural networks
represent various types of information, e.g., geographic information
goh2021multimodal; gurnee2023language, truth burns2022discovering;
marks2023geometry and the state of board games mcgrath2022acquisition;
toshniwal2022chess; li2022emergent. Another major MI thrust has been to
understand how neural networks perform algorithmic tasks, e.g., modular
arithmetic (nanda2023progress; liu2022towards; zhong2023clock;
quirke2023understanding), greater-than (hanna2023does), and greatest-common-
divisor charton2023can.

Whereas lindner2023tracr automatically convert traditional code into a neural
network, we aim to do the opposite. Other recent efforts to automate MI
include identifying a sparse subgraph of the network whose units are causally
relevant to a behavior of interest conmy2023towards; syed2023attribution and
using LLMs to label internal components of neural networks, for instance
neurons bills2023language and features discovered by sparse autoencoders
cunningham2023sparse; bricken2023monosemanticity.

##  3 MIPS, our program synthesis algorithm

Figure 1: The pipeline of our program synthesis method. MIPS relies on
discovering integer representations and bit representations of hidden states,
which enable regression methods to figure out the exact symbolic relations
between input, hidden, and output states.

As summarized in Figure 1, MIPS involves the following key steps.

  1. 1.

Neural network training

  2. 2.

Neural network simplification

  3. 3.

Finite state machine extraction

  4. 4.

Symbolic regression

Step 1 is to train a black-box neural network to learn an algorithm that
performs the desired task. In this paper, we use a recurrent neural network
(RNN) of the general form

$\displaystyle{\bf h}_{i}$ $\displaystyle=$ $\displaystyle f({\bf
h}_{i-1},{\bf x}_{i}),$ (1) $\displaystyle{\bf y}_{i}$ $\displaystyle=$
$\displaystyle g({\bf h}_{i}),$ (2)

that maps input vectors ${\bf x}_{i}$ into output vectors ${\bf y}_{i}$ via
hidden states ${\bf h}_{i}$. The RNN is defined by the two functions $f$ and
$g$, which are implemented as feed-forward neural networks (MLPs) to allow
more model expressivity than for a vanilla RNN. The techniques described below
can also be applied to more general neural network architectures.

Step 2 attempts to automatically simplify the learned neural network without
reducing its accuracy. Steps 3 and 4 automatically distill this simplified
learned algorithm into Python code. When the training data is discrete
(consisting of say text tokens, integers, or pixel colors), the neural network
will be a finite state machine: the activation vectors for each of its neuron
layers define finite sets and the entire working of the network can be defined
by look-up tables specifying the update rules for each layer. For our RNN,
this means that the space of hidden states ${\bf h}$ is discrete, so that the
functions $f$ and $g$ can be defined by lookup tables. As we will see below,
the number of hidden states that MIPS needs to keep track of can often be
greatly reduced by clustering them, corresponding to learned representations.
After this, the geometry of the cluster centers in the hidden space often
reveals that they form either an incomplete multidimensional lattice whose
points represent integer tuples, or a set whose cardinality is a power of two,
whose points represent Boolean tuples. In both of these cases, the
aforementioned lookup tables simply specify integer or Boolean functions,
which MIPS attempts to discover via symbolic regression. Below we present an
integer autoencoder and a Boolean autoencoder to discover such integer/Boolean
representations from arbitrary point sets.

We will now describe each of the three steps of MIPS in greater detail.

###  3.1 AutoML optimizing for simplicity

We wish to find the simplest RNN that can learn our task, to facilitate
subsequent discovery of the algorithm that it has learned. We therefore
implement an AutoML-style neural architecture search that tries to minimize
network size while achieving perfect test accuracy. This search space is
defined by a vector ${\bf p}$ of five main architecture hyperparameters: the
five integers ${\bf p}=(n,w_{f},d_{f},w_{g},d_{g})$ corresponding to the
dimensionality of hidden state ${\bf h}$, the width and depth of the
$f$-network, and the width and depth of the $g$-network, respectively. Both
the $f$\- and $g$-networks have a linear final layer and ReLU activation
functions for all previous layers. The hidden state ${\bf h}_{0}$ is
initialized to zero.

To define the parameter search space, we define ranges for each parameter. For
all tasks, we use $n\in\\{1,2,\ldots,128\\}$, $w_{f}\in\\{1,2,\ldots,256\\}$,
$d_{f}\in\\{1,2,3\\}$, $w_{g}\in\\{1,2,\ldots,256\\}$ and
$d_{g}\in\\{1,2,3\\}$, so the total search space consists of $128\times
256\times 3\times 256\times 3=75,497,472$ hyperparameter vectors ${\bf
p}_{i}$. We order this search space by imposing a strict ordering on the
importance of minimizing each hyperparameter – lower $d_{g}$ is strictly more
important than lower $d_{f}$, which is strictly more important than lower $n$,
which is strictly more important than lower $w_{g}$, which is strictly more
important than lower $w_{f}$. We aim to find the hyperparameter vector
(integer 5-tuple) $p_{i}$ in the search space which has lowest rank $i$ under
this ordering.

We search the space in the following simple manner. We first start at index
$i=65,536$, which corresponds to parameters $(1,1,2,1,1)$. For each parameter
tuple, we train networks using 5 different seeds. We use the loss function
$\ell(x,y)=\frac{1}{2}\log[1+(x-y)^{2}]$, finding that it led to more stable
training than using vanilla MSE loss. We train for either 10,000 or 20,000
steps, depending on the task, using the Adam optimizer, a learning rate of
$10^{-3}$, and batch size 4096. The test accuracy is evaluated with a batch of
65536 samples. If no networks achieve 100% test accuracy (on any test batch),
we increase $i$ by $2^{1/4}$. We proceed in this manner until we find a
network where one of the seeds achieves perfect test accuracy or until the
full range is exhausted. If we find a working network on this upwards sweep,
we then perform a binary search using the interval halving method, starting
from the successful $i$, to find the lowest $i$ where at least one seed
achieves perfect test accuracy.

###  3.2 Auto-simplification

After finding a minimal neural network architecture that can solve a task, the
resulting neural network weights typically seem random and un-interpretable.
This is because there exist symmetry transformations of the weights that leave
the overall input-output behavior of the neural network unchanged. The random
initialization of the network has therefore caused random symmetry
transformations to be applied to the weights. In other words, the learned
network belongs to an equivalence class of neural networks with identical
behavior and performance, corresponding to a submanifold of the parameter
space. We exploit these symmetry transformations to simplify the neural
network into a normal form, which in a sense is the simplest member of its
equivalence class. Conversion of objects into a normal/standard form is a
common concept in mathematics and physics (for example, conjunctive normal
form, wavefunction normalization, reduced row echelon form, and gauge fixing).

Two of our simplification strategies below exploit a symmetry of the RNN
hidden state space ${\bf h}$. We can always write the MLP $g$ in the form
$g({\bf h})=G({\bf U}{\bf h}+{\bf c})$ for some function $G$. So if $f$ is
affine, i.e., of the form $f({\bf h},{\bf x})={\bf W}{\bf h}+{\bf V}{\bf
x}+{\bf b}$, then the symmetry transformation

${\bf W}^{\prime}\equiv{\bf A}{\bf W}{\bf A}^{-1}$, ${\bf V}^{\prime}={\bf
A}{\bf V}$, ${\bf U}^{\prime}={\bf U}{\bf A}^{-1}$, ${\bf
h}^{\prime}\equiv{\bf A}{\bf h}$, ${\bf b}^{\prime}={\bf A}{\bf b}$ keeps the
RNN in the same form:

$\displaystyle{\bf h}_{i}^{\prime}$ $\displaystyle=$ $\displaystyle{\bf A}{\bf
h}_{i}={\bf A}{\bf W}{\bf A}^{-1}{\bf A}{\bf h}_{i-1}+{\bf A}{\bf V}{\bf
x}_{i}+{\bf A}{\bf b}$ (3) $\displaystyle=$ $\displaystyle{\bf
W}^{\prime-1}{\bf h}^{\prime}_{i-1}+{\bf V}^{\prime}{\bf x}_{i}+{\bf
b}^{\prime},$ $\displaystyle{\bf y}_{i}$ $\displaystyle=$ $\displaystyle
G({\bf U}{\bf h}_{i}+{\bf c})=G({\bf U}{\bf A}^{-1}{\bf h}^{\prime}_{i}+{\bf
c})$ (4) $\displaystyle=$ $\displaystyle G({\bf U}^{\prime}{\bf
h}^{\prime}_{i}+{\bf c}).$

We think of neural networks as nails, which can be hit by various auto-
normalization hammers. Each hammer is an algorithm that applies
transformations to the weights to remove degrees of freedom caused by extra
symmetries or cleans the neural network up in some other way. In this section,
we describe five normalizers we use to simplify our trained networks, termed
“Whitening”, “Jordan normal form”, “Toeplitz”, “De-bias”, and “Quantization”.
For every neural network, we always apply this sequence of normalizers in that
specific order, for consistency. We describe them below and provide additional
details about them in the Appendix LABEL:sec:hammer_details.

  1. 1.

Whitening: Just as we normalize input data to use for training neural
networks, we would like activations in the hidden state space $\mathbf{h}_{i}$
to be normalized. To ensure normalization in all directions, we feed the
training dataset into the RNN, collect all the hidden states, compute the
uncentered covariance matrix ${\bf C}$, and then apply a whitening transform
${\bf h}\mapsto{\bf C}^{-1/2}{\bf h}$ to the hidden state space so that its
new covariance becomes the identity matrix. This operation exists purely to
provide better numerical stability to the next step.

  2. 2.

Jordan normal form: When the function $g$ is affine, we can apply the
aforementioned symmetry transformation to try to diagonalize ${\bf W}$, so
that none of the hidden state dimensions interact with one another.
Unfortunately, not all matrices ${\bf W}$ can be diagonalized, so we use a
generalized alternative: the Jordan normal form, which allows elements of the
superdiagonal to be either zero or one. To eliminate complex numbers, we also
apply $2\times 2$ unitary transformations to eigenvectors corresponding to
conjugate pairs of complex eigenvalues afterward. The aforementioned whitening
is now ruined, but it helped make the Jordan normal form calculation more
numerically stable.

  3. 3.

Toeplitz: Once ${\bf W}$ is in Jordan normal form, we divide it up into Jordan
blocks and apply upper-triangular Toeplitz transformations to the dimensions
belonging to each Jordan block. There is now an additional symmetry,
corresponding to multiplying each Jordan block by an upper triangular Toeplitz
matrix, and we exploit the Toeplitz matrix that maximally simplifies the
aforementioned ${\bf V}$-matrix.

  4. 4.

De-bias: Sometimes ${\bf W}$ is not full rank, and ${\bf b}$ has a component
in the direction of the nullspace. In this case, the component can be removed,
and the bias ${\bf c}$ can be adjusted to compensate.

  5. 5.

Quantization: After applying all the previous normalizers, many of the weights
may have become close to integers, but not exactly due to machine precision
and training imperfections. Sometimes, depending on the task, all of the
weights can become integers. We therefore round any weights that are within
$\epsilon\equiv 0.01$ of an integer to that integer.

###  3.3 Boolean and integer autoencoders

Figure 2: These hidden structures can be turned into discrete representations.
Left: the hidden states for the bitstring addition task are seen to form four
clusters, corresponding to 2 bits: the output bit and the carry bit. Right:
the hidden states for the Sum_Last2 task are seen to form clusters on a 2D
lattice corresponding to two integers.

As mentioned, our goal is to convert a trained recurrent neural network (RNN)
into a maximally simple (Python) program that produces equivalent input-output
behavior. This means that if the RNN has 100% accuracy for a given dataset, so
should the program, with the added benefit of being more interpretable,
precise, and verifiable.

Once trained/written, the greatest difference between a neural network and a
program implementing the same finite state machine is that the former is fuzzy
and continuous, while the latter is precise and discrete. To convert a neural
network to a program, some discretization (“defuzzification”) process is
needed to extract precise information from seemingly noisy representations.
Fortunately, mechanistic interpretability research has shown that neural
networks tend to learn meaningful, structured knowledge representations for
algorithmic tasks liu2022towards; nanda2023progress. Previous interpretability
efforts typically involved case-by-case manual inspection, and only gained
algorithmic understanding at the level of pseudocode at best. We tackle this
more ambitious question: can we create an automated method that distills the
learned representation and associated algorithms into an equivalent (Python)
program?

Since the tasks in our benchmark involve bits and integers, which are already
discrete, the only non-discrete parts in a recurrent neural network are its
hidden representations. Here we show two cases when hidden states can be
discretized: they are (1) a bit representation or (2) a (typically incomplete)
integer lattice. Generalizing to the mixed case of bits and integers is
straightforward. Figure 2 shows all hidden state activation vectors ${\bf
h}_{i}$ for all steps with all training examples for two of our tasks. The
left panel shows that the $10^{4}$ points ${\bf h}_{i}$ form $2^{2}=4$ tight
clusters, which we interpret as representing 2 bits. The right panel reveals
that the points ${\bf h}_{i}$ form an incomplete 2D lattice that we interpret
as secretly representing a pair of integers.

Bit representations

The hidden states for the 2 bits in Figure 2 are seen to form a parallelogram.
More generally, we find that hidden states encode $b$ bits as $2^{b}$
clusters, which in some cases form $b$-dimensional parallelograms and in other
cases look more random. Our algorithm tries all $(2^{b})!$ possible
assignments of the $2^{b}$ clusters to bitstrings of length $b$ and selects
the assignment that minimizes the length of the resulting Python program.

Integer lattice

As seen in Figure 2, the learned representation of an integer lattice tends to
be both non-square (deformed by a random affine transformation) and sparse
(since not all integer tuplets occur during training). We thus face the
following problem: given (possibly sparse) samples of points ${\bf h}_{i}$
from an $n$-dimensional lattice, how can we reconstruct the integer lattice in
the sense that we figure out which integer tuple each lattice point
represents? We call the solution an integer autoencoder since it compresses
any point set into a set of integer tuples from which the original points can
be at least approximately recovered as ${\bf h}_{i}={\bf A}{\bf k}_{i}+{\bf
b}$, where ${\bf A}$ is a matrix and ${\bf b}$ is a vector that defines the
affine transformation and a set of integer vectors ${\bf k}_{i}$.

In the Appendix LABEL:app:gcd, we present a solution that we call the GCD
lattice finder. For the special case $n=1$, its core idea is to compute the
greatest common denominator of pairwise separations: for example, for the
points $\\{1.7,3.2,6.2,7.7...\\}$, all point separations are divisible by
$A=1.5$, from which one infers that $b=0.2$ and the lattice can be rewritten
as $1.5\times${1,2,4,5}$+0.2$. For multidimensional lattices, our algorithm
uses the GCD of ratios of generalized cell volumes to infer the directions and
lengths of the lattice vectors that form the columns of ${\bf A}$.

For the special case where the MLP defining the function $f$ is affine or can
be accurately approximated as affine, we use a simpler method we term the
Linear lattice finder, also described in Appendix LABEL:app:linear-lattice-
finder. Here the idea is to exploit that the lattice is simply an affine
transformation of a regular integer lattice (the input data), so we can simply
“read off” the desired lattice basis vectors from this affine transformation.

Symbolic regression

Once the hidden states ${\bf h}_{i}$ have been successfully mapped to Boolean
or integer tuples as described above, the functions $f$ and $g$ that specify
the learned RNN can be re-expressed as lookup tables, showing their
Boolean/integer output tuple for each Boolean/integer input tuple. All that
remains is now symbolic regression, i.e., discovering the simplest possible
symbolic formulae that define $f$ and $g$.

Boolean regression: In the case where a function maps bits to a bit, our
algorithm determines the following set of correct Boolean formulae and then
returns the shortest one. The first candidate formula is the function written
in disjunctive normal form, which is always possible. If the Boolean function
is symmetric, i.e., invariant under all permutations of its arguments, then we
also write it as an integer function of its bit sum.

Integer regression: In the case when a function maps integers to an integer,
we try the following two methods:

  1. 1.

If the function is linear, then we perform simple linear regression, round the
resulting coefficients to integers, and simplify, e.g., multiplications by 0
and 1.

  2. 2.

Otherwise, we use the brute-force symbolic solver from AI Feynman
(udrescu2020ai2), including the 6 unary operations $\\{>,<,\sim,H,D,A\\}$ and
4 binary operations $\\{+,-,*,\%\\}$ whose meanings are explained in Appendix
LABEL:app:symbolic-regression, then convert the simplest discovered formula
into Python format.

Once symbolic formulas have been separately discovered for each component of
the vector-valued functions $f$ and $g$, we insert them into a template Python
program that implements the basic loop over inputs that are inherent in an
RNN. We present examples of our auto-generated programs in Figures
LABEL:fig:bit_addition_program and LABEL:fig:hammer_comparison and in Appendix
LABEL:app:generated-programs.

##  4 Results

We will now test the program synthesis abilities of our MIPS algorithm on a
benchmark of algorithmic tasks specified by numerical examples. For
comparison, we try the same benchmark on GPT-4 Turbo, which is currently (as
of January 2024) described by OpenAI as their latest generation model, with a
128k context window and more capable than the original GPT-4.

###  4.1 Benchmark

Our benchmark consists of the 62 algorithmic tasks listed in Table 1. They
each map one or two integer lists of length 10 or 20 into a new integer list.
We refer to integers whose range is limited to $\\{0,1\\}$ as bits. We
generated this task list manually, attempting to produce a collection of
diverse tasks that would in principle be solvable by an RNN. We also focused
on tasks whose known algorithms involved majority, minimum, maximum, and
absolute value functions because we believed they would be more easily
learnable than other nonlinear algorithms due to our choice of the ReLU
activation for our RNNs. The benchmark training data and project code is
available at https://github.com/ejmichaud/neural-verification. The tasks are
described in Table 1, with additional details in Appendix
LABEL:extra_task_explanation.

Since the focus of our paper is not on whether RNNs can learn algorithms, but
on whether learned algorithms can be auto-extracted into Python, we discarded
from our benchmark any generated tasks on which our RNN-training failed to
achieve 100% accuracy.

Our benchmark can never show that MIPS outperforms any large language model
(LLM). Because LLMs are typically trained on GitHub, many LLMs can produce
Python code for complicated programming tasks that fall outside of the class
we study. Instead, the question that our MIPS-LLM comparison addresses is
whether MIPS complements LLMs by being able to solve some tasks where an LLM
fails.

###  4.2 Evaluation

For both our method and GPT-4 Turbo, a task is considered solved if and only
if a Python program is produced that solves the task with 100% accuracy. GPT-4
Turbo is prompted using the “chain-of-thought” approach described below and
illustrated in LABEL:fig:code_generation_process.

For a given task, the LLM receives two lists of length 10 sourced from the
respective RNN training set. The model is instructed to generate a formula
that transforms the elements of list “x” (features) into the elements of list
‘y’ (labels). Subsequently, the model is instructed to translate this formula
into Python code. The model is specifically asked to use elements of the
aforementioned lists as a test case and print “Success” or “Failure” if the
generated function achieves full accuracy on the test case. An external
program extracts a fenced markdown codeblock from the output, which is saved
to a separate file and executed to determine if it successfully completes the
task. To improve the chance of success, this GPT-4 Turbo prompting process is
repeated three times, requiring only at least one of them to succeed. We run
GPT using default temperature settings.

Table 1: Benchmark results. For tasks with note “see text”, please refer to Appendix LABEL:extra_task_explanation Task # |  Input Strings |  Element Type | Task Description | Task Name |  Solved by GPT-4? |  Solved by MIPS?
---|---|---|---|---|---|---
1 |  2 |  bit | Binary addition of two bit strings | Binary_Addition |  0 |  1
2 |  2 |  int | Ternary addition of two digit strings | Base_3_Addition |  0 |  0
3 |  2 |  int | Base 4 addition of two digit strings | Base_4_Addition |  0 |  0
4 |  2 |  int | Base 5 addition of two digit strings | Base_5_Addition |  0 |  0
5 |  2 |  int | Base 6 addition of two digit strings | Base_6_Addition |  1 |  0
6 |  2 |  int | Base 7 addition of two digit strings | Base_7_Addition |  0 |  0
7 |  2 |  bit | Bitwise XOR | Bitwise_Xor |  1 |  1
8 |  2 |  bit | Bitwise OR | Bitwise_Or |  1 |  1
9 |  2 |  bit | Bitwise AND | Bitwise_And |  1 |  1
10 |  1 |  bit | Bitwise NOT | Bitwise_Not |  1 |  1
11 |  1 |  bit | Parity of last 2 bits | Parity_Last2 |  1 |  1
12 |  1 |  bit | Parity of last 3 bits | Parity_Last3 |  0 |  1
13 |  1 |  bit | Parity of last 4 bits | Parity_Last4 |  0 |  0
14 |  1 |  bit | Parity of all bits seen so far | Parity_All |  0 |  1
15 |  1 |  bit | Parity of number of zeros seen so far | Parity_Zeros |  0 |  1
16 |  1 |  int | Cumulative number of even numbers | Evens_Counter |  0 |  0
17 |  1 |  int | Cumulative sum | Sum_All |  1 |  1
18 |  1 |  int | Sum of last 2 numbers | Sum_Last2 |  0 |  1
19 |  1 |  int | Sum of last 3 numbers | Sum_Last3 |  0 |  1
20 |  1 |  int | Sum of last 4 numbers | Sum_Last4 |  1 |  1
21 |  1 |  int | Sum of last 5 numbers | Sum_Last5 |  1 |  1
22 |  1 |  int | sum of last 6 numbers | Sum_Last6 |  1 |  1
23 |  1 |  int | Sum of last 7 numbers | Sum_Last7 |  1 |  1
24 |  1 |  int | Current number | Current_Number |  1 |  1
25 |  1 |  int | Number 1 step back | Prev1 |  1 |  1
26 |  1 |  int | Number 2 steps back | Prev2 |  1 |  1
27 |  1 |  int | Number 3 steps back | Prev3 |  1 |  1
28 |  1 |  int | Number 4 steps back | Prev4 |  1 |  1
29 |  1 |  int | Number 5 steps back | Prev5 |  1 |  1
30 |  1 |  int | 1 if last two numbers are equal | Previous_Equals_Current |  0 |  1
31 |  1 |  int | $\text{current}-\text{previous}$ | Diff_Last2 |  0 |  1
32 |  1 |  int | $\lvert\text{current}-\text{previous}\rvert$ | Abs_Diff |  0 |  1
33 |  1 |  int | $\lvert\text{current}\rvert$ | Abs_Current |  1 |  1
34 |  1 |  int | $\lvert\text{current}\rvert-\lvert\text{previous}\rvert$ | Diff_Abs_Values |  1 |  0
35 |  1 |  int | Minimum of numbers seen so far | Min_Seen |  1 |  0
36 |  1 |  int | Maximum of integers seen so far | Max_Seen |  1 |  0
37 |  1 |  int | integer in 0-1 with highest frequency | Majority_0_1 |  1 |  0
38 |  1 |  int | Integer in 0-2 with highest frequency | Majority_0_2 |  0 |  0
39 |  1 |  int | Integer in 0-3 with highest frequency | Majority_0_3 |  0 |  0
40 |  1 |  int | 1 if even, otherwise 0 | Evens_Detector |  1 |  0
41 |  1 |  int | 1 if perfect square, otherwise 0 | Perfect_Square_Detector |  0 |  0
42 |  1 |  bit | 1 if bit string seen so far is a palindrome | Bit_Palindrome |  1 |  0
43 |  1 |  bit | 1 if parentheses balanced so far, else 0 | Balanced_Parenthesis |  0 |  0
44 |  1 |  bit | Number of bits seen so far mod 2 | Parity_Bits_Mod2 |  1 |  0
45 |  1 |  bit | 1 if last 3 bits alternate | Alternating_Last3 |  0 |  0
46 |  1 |  bit | 1 if last 4 bits alternate | Alternating_Last4 |  1 |  0
47 |  1 |  bit | bit shift to right (same as prev1) | Bit_Shift_Right |  1 |  1
48 |  2 |  bit | Cumulative dot product of bits mod 2 | Bit_Dot_Prod_Mod2 |  0 |  1
49 |  1 |  bit | Binary division by 3 (see text) | Div_3 |  1 |  0
50 |  1 |  bit | Binary division by 5 (see text) | Div_5 |  0 |  0
51 |  1 |  bit | Binary division by 7 (see text) | Div_7 |  0 |  0
52 |  1 |  int | Cumulative addition modulo 3 | Add_Mod_3 |  1 |  1
53 |  1 |  int | Cumulative addition modulo 4 | Add_Mod_4 |  0 |  0
54 |  1 |  int | Cumulative addition modulo 5 | Add_Mod_5 |  0 |  0
55 |  1 |  int | Cumulative addition modulo 6 | Add_Mod_6 |  0 |  0
56 |  1 |  int | Cumulative addition modulo 7 | Add_Mod_7 |  0 |  0
57 |  1 |  int | Cumulative addition modulo 8 | Add_Mod_8 |  0 |  0
58 |  1 |  int | 1D dithering, 4-bit to 1-bit (see text) | Dithering |  1 |  0
59 |  1 |  int | Newton’s of - freebody (integer input) | Newton_Freebody |  0 |  1
60 |  1 |  int | Newton’s law of gravity (see text) | Newton_Gravity |  0 |  1
61 |  1 |  int | Newton’s law w. spring (see text) | Newton_Spring |  0 |  1
62 |  2 |  int | Newton’s law w. magnetic field (see text) | Newton_Magnetic |  0 |  0
|  |  | Total solved |  |  30 |  32

###  4.3 Performance

As seen in Table 1, MIPS is highly complementary to GPT-4 Turbo: MIPS solves
32 of our tasks, including 13 that are not solved by ChatGPT-4 (which solves
30).

The AutoML process of Section 3.1 discovers networks of varying task-dependent
shape and size. LABEL:architecture_search_table shows the parameters ${\bf p}$
discovered for each task. Across our 62 tasks, 16 tasks could be solved by a
network with hidden dimension $n=1$, and the largest $n$ required was 81. For
many tasks, there was an interpretable meaning to the shape of the smallest
network we discovered. For instance, on tasks where the output is the element
occurring $k$ steps earlier in the list, we found $n=k+1$, since the current
element and the previous $k$ elements must be stored for later recall.

We found two main failure modes for MIPS:

  1. 1.

Noise and non-linearity. The latent space is still close to being a finite
state machine, but the non-linearity and/or noise present in an RNN is so
dominant that the integer autoencoder fails, e.g., for Diff_Abs_Values. Humans
can stare at the lookup table and regress the symbolic function with their
brains, but since the lookup table is not perfect, i.e., has the wrong integer
in a few examples, MIPS fails to symbolically regress the function. This can
probably be mitigated by learning and generalizing from a training subset with
a smaller dynamic range.

  2. 2.

Continuous computation. A key assumption of MIPS is that RNNs are finite-state
machines. However, RNNs can also use continuous variables to represent
information — the Majority_0_X tasks fail for this reason. This can probably
be mitigated by identifying and implementing floating-point variables.

⬇

1

2def f(s,t):

3 a = 0;b = 0;

4 ys = []

5 for i in range(10):

6 c = s[i]; d = t[i];

7 next_a = b ^ c ^ d

8 next_b = b+c+d>1

9 a = next_a;b = next_b;

10 y = a

11 ys.append(y)

12 return ys \end{lstlisting}

13 % \centering

14 % \caption{With normalizers.}

15 % \label{fig:better_rnn_sum_last5_numerical}

16 % \end{subfigure}

17 \caption{The generated program for the addition of two binary numbers
represented as bit sequences. Note that MIPS rediscovers the ‘‘ripple adder",
where the variable $b$ above is the carry bit.}

18 \label{fig:bit_addition_program}

19\end{figure}

20

21\Fig{fig:bit_addition_program} shows an example of a MIPS rediscovering the
"ripple-carry adder" algorithm.

22The normalizers significantly simplified some of the resulting programs, as
illustrated in \fig{fig:hammer_comparison}, and sometimes made the difference
between MIPS failing and succeeding.

23We found that applying a small $L1$ weight regularization sometimes
facilitated integer autoencoding by axis-aligning the lattice.

24

25\begin{figure}

26 % \begin{subfigure}

27 \begin{lstlisting}[language=Python]

28def f(s):

29 a = 198;b = -11;c = -3;d = 483;e = 0;

30 ys = []

31 for i in range(20):

32 x = s[i]

33 next_a = -b+c+190

34 next_b = b-c-d-e+x+480

35 next_c = b-e+8

36 next_d = -b+e-x+472

37 next_e = a+b-e-187

38 a = next_a;b = next_b;c = next_c;d = next_d;e = next_e;

39 y = -d+483

40 ys.append(y)

41 return ys\end{lstlisting}

42 % \centering

43 % \caption{Without normalizers.}

44 % \label{fig:worse_rnn_sum_last5_numerical}

45 % \end{subfigure}

46 % \begin{subfigure}

47 \begin{lstlisting}[language=Python]

48def f(s):

49 a = 0;b = 0;c = 0;d = 0;e = 0;

50 ys = []

51 for i in range(20):

52 x = s[i]

53 next_a = +x

54 next_b = a

55 next_c = b

56 next_d = c

57 next_e = d

58 a = next_a;b = next_b;c = next_c;d = next_d;e = next_e;

59 y = a+b+c+d+e

60 ys.append(y)

61 return ys\end{lstlisting}

62 % \centering

63 % \caption{With normalizers.}

64 % \label{fig:better_rnn_sum_last5_numerical}

65 % \end{subfigure}

66 \caption{Comparison of code generated from an RNN trained on Sum\\_Last5,
with (top) and without (top) normalizers. The whitening normalizer provided
numerical stability to the Jordan normal form normalizer, which itself
simplified the recurrent portion of the program. The Toeplitz and de-biasing
normalizers jointly sparsified the occurrences of $x$ in the program, and the
number of terms required to compute $y$. The quantization normalizer enabled
all variables to be represented as integers.}

67 \label{fig:hammer_comparison}

68\end{figure}

69

70

71%* Are there any interesting patterns for where GPT-4 beats MIPS or vice
versa?

72

73

74% Please add the following required packages to your document preamble:

75% \usepackage{booktabs}

76% \usepackage{graphicx}

77

78

79\begin{figure}[htbp]

80\resizebox{\columnwidth}{!}{% Resize to fit within a single column

81\centering

82\begin{tikzpicture}[

83 auto,

84 node distance=0.5cm and 0.25cm, % vertical and horizontal distance between
nodes

85 >=Latex, % arrow tip style

86 % Style for different types of nodes

87 start/.style={draw, rectangle, fill=green!30, text width=5cm, text
centered, minimum height=2em},

88 io/.style={draw, rectangle, rounded corners, fill=blue!30, text width=3cm,
text centered, minimum height=3em},

89 process/.style={draw, rectangle, fill=orange!30, text width=5cm, text
centered, minimum height=3em},

90 decision/.style={draw, diamond, aspect=2, fill=yellow!30, text width=5cm,
text badly centered, inner sep=0pt},

91 arrow/.style={->, thick},

92 dottedline/.style={draw, thick, dotted, -Latex}]

93

94% Nodes

95\node (start) [start, xshift=-5cm] {Conversation Start};

96\node (user1) [io, below=of start] {User: "Each row in the table below
contains two lists...give me a formula for ..."};

97\node (gpt1) [process, below=of user1] {GPT: [Response]};

98\node (user2) [io, below=of gpt1] {User: "Please write a Python program to
..."};

99\node (gpt2) [process, below=of user2] {GPT: [Response]};

100\node (codeBlock) [process, below=of gpt2, ] {Extracted Code Block};

101\node (decision) [decision, below=of codeBlock] {Success or Failure?};

102\node (success) [start, below left=of decision, xshift=-0.02cm] {Success};

103\node (failure) [start, below right=of decision, xshift=0.02cm] {Failure};

104

105% Arrows

106\draw [arrow] (start) \-- (user1);

107\draw [arrow] (user1) \-- (gpt1);

108\draw [arrow] (gpt1) \-- (user2);

109\draw [arrow] (user2) \-- (gpt2);

110\draw [dottedline] (gpt2) \-- (codeBlock);

111\draw [dottedline] (codeBlock) \-- (decision);

112\draw [arrow] (decision) \-- (success);

113\draw [arrow] (decision) \-- (failure);

114\end{tikzpicture}}

115

116\caption{We compare MIPS against program synthesis with the large language
model GPT-4 Turbo, prompted with a ‘‘chain-of-thought" approach. It begins
with the user providing a task, followed by the model’s response, and
culminates in assessing the success or failure of the generated Python code
based on its accuracy in processing the provided lists.}

117\label{fig:code_generation_process}

118\end{figure}

119

120

121

122

123

124

125\section{Conclusions}

126

127% WHAT WE’VE DONE

128

129We have presented MIPS, a novel method for program synthesis based on
automated mechanistic interpretability of neural networks trained to perform
the desired task, auto-distilling the learned algorithm into Python code.

130Its essence is to first train a recurrent neural network to learn a clever
finite state machine that performs the task, and then automatically figure out
how this machine works.

131

132\subsection{Findings}

133

134We found MIPS highly complementary to LLM-based program synthesis with
GPT-4 Turbo, with each approach solving many tasks that stumped the other.

135Whereas LLM-based methods have the advantage of drawing upon a vast corpus
of human training data, MIPS has the advantage of discovering algorithms from
scratch without human hints, with the potential to discover entirely new
algorithms. As opposed to genetic programming approaches, MIPS leverages the
power of deep learning by exploiting gradient information.

136

137Program synthesis aside, our results shed further light on mechanistic
interpretability, specifically on how neural networks represent bits and
integers. We found that $n$ integers tend to get encoded linearly in $n$
dimensions, but generically in non-orthogonal directions with an additive
offset. This is presumably because there are many more such messy encodings
than simple ones, and the messiness can be easily (linearly) decoded. We saw
that $n$ bits sometimes get encoded as an $n$-dimensional parallelogram, but
not always ––– possibly because linear decodability is less helpful when the
subsequent bit operations to be performed are nonlinear anyway.

138

139

140

141

142

143\subsection{Outlook}

144

145Our work is merely a modest first attempt at mechanistic-interpretability-
based program synthesis, and there are many obvious generalizations worth
trying in future work. For example:

146\begin{enumerate}

147\item Improvements in training and integer autoencoding (since many of our
failed examples failed only just barely)

148\item Generalization from RNNs to other architectures such as transformers

149\item Generalization from bits and integers to more general extractable
data types such as floating-point numbers and various discrete mathematical
structures and knowledge representations

150\item Scaling to tasks requiring much larger neural networks

151\item Automated formal verification of synthesized programs (we perform
such verification with Dafny

152in \Cref{app:dafnyverification} to show that our MIPS-learned ripple adder
correctly adds {\it any} binary numbers, not merely those in the test set, but
such manual work should ideally be fully automated)

153\end{enumerate}

154

155LLM-based coding co-pilots are already highly useful for program synthesis
tasks based on verbal problem descriptions or auto-complete, and will only get
better. MIPS instead tackles program synthesis based on test cases alone.

156This makes it analogous to {\it symbolic regression}
\cite{udrescu2020ai2,cranmer2023interpretable}, which has already proven
useful for various science and engineering applications
\cite{cranmer2020discovering,ma2022evolving} where one wishes to approximate
data relationships with symbolic formulae.

157The MIPS framework generalizes symbolic regression from feed-forward
formulae to programs with loops, which are in principle Turing complete.

158If this approach can be scaled up, it may enable promising opportunities
for making machine-learned algorithms more interpretable, verifiable, and
trustworthy.

159

160

161

162\section*{Broader Impact}

163

164Because machine-learned algorithms now outperform traditional human-
discovered algorithms on many tasks, there are incentives to deploy them even
without a full understanding of how they work and of whether they are biased,
unsafe, or otherwise problematic. The aspirational broader impact motivating
this paper is to help automate the process of making AI systems more
transparent, robust, and trustworthy, with the ultimate goal of developing
provably safe AI systems

165\cite{tegmark2023provably}.

166

167\section*{Acknowledgements}

168

169%{\bf [COMMENT OUT FOR ANONYMOUS SUBMISION!]}

170We thank Wes Gurnee, James Liu, and Armaun Sanayei for helpful
conversations and suggestions. This work is supported by Erik Otto, Jaan
Tallinn, the Rothberg Family Fund for Cognitive Science, the NSF Graduate
Research Fellowship (Grant No.

1712141064), and IAIFI through NSF grant PHY-2019786.

172

173

174\bibliography{refs}

175\bibliographystyle{icml2024}

176

177

178%* Zimings sharp-fuzzy intuition

179

180

181\clearpage

182

183

184\appendix

185

186\onecolumn

187

188%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

189

190\begin{table*}[t]

191\caption{AutoML architecture search results. All networks achieved 100\%
accuracy on at least one test batch.}

192\label{architecture_search_table}

193\vskip 0.15in

194\begin{center}

195\begin{small}

196% \begin{sc}

197\renewcommand{\arraystretch}{0.97} % Reducing vertical spacing

198\begin{tabular}{llccccccc}

199\toprule

200Task \# & Task Name & $\nhidden$ & $\fwidth$ & $\fdepth$ & $\gwidth$ &
$\gdepth$ & Train Loss & Test Loss \\\

201\midrule

202% Include the lines generated by your Python script here

203\input{tables/architecture_search_results}

204% \midrule

205\end{tabular}

206% \end{sc}

207\end{small}

208\end{center}

209\vskip -0.1in

210\end{table*}

211

212\section{Lattice finding using generalized greatest common divisor (GCD)}
\label{app:gcd}

213

214Our method often encounters cases where hidden states secretly form an
affine transformation of an integer lattice. However, not all lattice points
are observed in training samples, so our goal is to recover the hidden integer
lattice from sparse observations.

215

216\subsection{Problem formulation}

217Suppose we have a set of lattice points in $\mathbb{R}^D$

218spanned by $D$ independent basis vectors, $\mat{b}_i \,(i=1,2,\cdots,D)$.
Each lattice point $j$ has the position

219\begin{equation}\label{eq:lat}

220 \mat{x}_j = \sum_{i=1}^D a_{ji} \mat{b}_i + \mat{c},

221\end{equation}

222where $\mat{c}$ is a global translation vector, and the coefficients
$a_{ji}$ are integers

223

224Our problem: given $N$ such data points
$(\mat{x}_1,\mat{x}_2,\cdots,\mat{x}_N)$, how can we recover the integer
coefficients $a_{ji}$ for each point data point as well as $\mat{b}_i$ and
$\mat{c}$?

225

226Note that even when the whole lattice is given, there are still degrees of
freedom for the solution. For example, $\\{\mat{c}\mapsto \mat{c}+\mat{b}_i,
a_{ji}\mapsto a_{ji}-1\\}$ remains a solution, and $\\{\mat{b}_i\to
\sum_{j=1}^D\Lambda_{ij}\mat{b}_j\\}$ remains a solution if $\mat{\Lambda}$ is
an integer matrix whose determinant is $\pm 1$. So our success criterion is:
(1) $a_{ji}$ are integers; (2) the discovered bases and the true bases have
the same determinant (the volume of a unit cell). Once a set of bases is
found, we can simplify them by minimizing their total norms over valid
transformations ($\mat{\Lambda}\in\mathbb{Z}^{D\times D}, {\rm
det}(\mat{\Lambda})=\pm 1$).

227

228\subsection{Regular GCD}

229

230As a reminder, given a list of $n$ numbers $\\{y_1, y_2, \cdots, y_n\\}$, a
common divisor $d$ is a number such that for all $i$, $\frac{y_i}{d}$ is an
integer. All common divisors are the set $\\{d|y_i/d\in\mathbb{Z}$, and the
greatest common divisor (GCD) is the largest number in this set. Because

231\begin{equation}

232 {\rm GCD}(y_1,\cdots,y_n) = {\rm GCD}(y_1, {\rm GCD}(y_2, {\rm
GCD}(y_3,...))),

233\end{equation}

234it without loss of generality suffices to consider the case $n=2$. A common
algorithm to compute GCD of two number is the so-called Euclidean algorithm.
We start with two numbers $r_0$, $r_1$ and $r_0 > r_1$, which is step 0. For
the $k^{\rm th}$ step, we perform division-with-remainder to find the quotient
$q_k$ and the remainder $r_k$ so that

235$r_{k-2} = q_k r_{k-1} + r_k$ with $|r_{k-1}| > |r_{k}|$~\footnote{We are
considering a general case where $r_0$ and $r_1$ may be negative. Otherwise
$r_k$ can always be positive numbers, hence no need to use the absolute
function.}. The algorithm will eventually produce a zero remainder $r_N=0$,
and the other non-zero remainder $r_{N-1}$ is the greatest common divisor.

236For example, ${\rm GCD}(55,45)=5$, because

237\begin{equation}

238 \begin{aligned}

239 55 & = 1 \times 45 + 10,\\\

240 45 & = 4 \times 10 + 5,\\\

241 10 & = 2 \times 5 + 0.

242 \end{aligned}

243\end{equation}

244

245\subsection{Generalized GCD in $D$ dimensions}

246

247Given a list of $n$ vectors $\\{\mat{y}_1,\mat{y}_2,\cdots,\mat{y}_n\\}$
where $\mat{y}_i\in\mathbb{R}^D$, and assuming that these vectors are in the
lattice described by Eq.~(\ref{eq:lat}), we can without loss of generality set
$\mat{c}=0$, since we can always redefine the origin. In $D$ dimensions, the
primitive of interest is the $D$-dimensional parallelogram: a line segment for
$D=1$ (one basis vector), a parallelogram for $D=2$ (two basis vectors),

248parallelepiped for $D=3$ (three basis vectors), \etc

249

250One can construct a $D$-dimensional parallelogram by constructing its basis
vectors as a linear integer combination of $\mat{y}_j$, i.e.,

251

252\begin{equation}

253 \mat{q}_i = \sum_{j=1}^n m_{ij}\mat{y}_j, m_{ij}\in\mathbb{Z},
i=1,2,\cdots, D.

254\end{equation}

255The goal of $D$-dimensional GCD is to find a ‘‘minimal’’ parallelogram,
such that its volume (which is ${\rm
det}(\mat{q}_1,\mat{q}_2,\cdots,\mat{q}_D)$) is GCD of volumes of other
possible parallelograms. Once the minimal parallelogram is
found~\footnote{There could be many minimal parallelograms, but finding one is
sufficient.}, we can also determine $\mat{b}_i$ in Eq.~(\ref{eq:lat}), since
$\mat{b}_i$ are exactly $\mat{q}_i$! To find the minimal parallelogram, we
need two steps: (1) figure out the unit volume; (2) figure out $\mat{q}_i
(i=1,2,\cdots)$ whose volume is the unit volume.

256

257{\bf Step 1: Compute unit volume $V_0$.} We first define
\textit{representative} parallelograms as one where all $i=1,2,\cdots,D$,
$\mat{m}_i\equiv (m_{i1},m_{i2},\cdots,m_{iD})$ are one-hot vectors, \ie, with
only one element being 1 and 0 otherwise. It is easy to show that the volume
of any parallelogram is a linear integer combination of

258volumes of representative parallelograms, so WLOG we can focus on
representative parallelograms. We compute the volumes of all representative
parallelograms, which gives a volume array. Since volumes are just scalars, we
can get the unit volume $V_0$ by calling the regular GCD of the volume array.

259

260{\bf Step 2: Find a minimal parallelogram (whose volume is the unit volume
computed in step 1).} Recall that in regular GCD, we are dealing with two
numbers (scalars). To leverage this in the vector case, we need to create
scalars out of vectors, and make sure that the vectors share the same linear
structure as the scalars so that we can extend division-and-remainder to
vectors. A natural scalar is volume. Now consider two parallelograms P1 and
P2, which share $D-1$ basis vectors $(\mat{y}_3,\dots,\mat{y}_{D+1})$, but
last basis vector is different: $\mat{y}_1$ for P1 and $\mat{y}_2$ for P2.
Denote their volume as $V_1$ and $V_2$:

261\begin{equation}

262 \begin{aligned}

263 V_1 &= {\rm det}(\mat{y}_1,\mat{y}_3,\mat{y}_4,\dots,\mat{y}_D) \\\

264 V_2 &= {\rm det}(\mat{y}_2,\mat{y}_3,\mat{y}_4,\dots,\mat{y}_D) \\\

265 \end{aligned}

266\end{equation}

267Since

268\begin{equation}

269 aV_1 + bV_2 = {\rm det}(a\mat{y}_1 +
b\mat{y}_2,\mat{y}_3,\mat{y}_4,\dots,\mat{y}_D),

270\end{equation}

271which shows that $(V_1, V_2)$ and $(\mat{y}_1,\mat{y}_2)$ share the same
linear structure. We can simply apply division-and-remainder to $V_1$ and
$V_2$ as in regular GCD:

272\begin{equation}

273 V_1’, V_2’ = {\rm GCD}(V_1, V_2),

274\end{equation}

275whose quotients in all iterations are saved and transferred to $\mat{y}_1$
and $\mat{y}_2$:

276\begin{equation}

277 \mat{y}_1’,\mat{y}_2’ = {\rm
GCD\_with\_predefined\_quotients}(\mat{y}_1,\mat{y}_2).

278\end{equation}

279If $V_1 = V_0$ (which is the condition for minimal parallelogram), the
algorithm terminates and returns
$(\mat{y}_1’,\mat{y}_3,\mat{y}_4,\cdots,\mat{y}_D)$. If $V_1>V_0$, we need to
repeat step 2 with the new vector list
$\\{\mat{y}_1’,\mat{y}_3,\cdots,\mat{y}_N\\}$.

280

281{\bf Why can we remove $\mat{y}_2’$ for next iteration?} Note that although
eventually $V_1’>0$ and $V_2’=0$, typically $\mat{y}_2\neq 0$. However, since

282\begin{equation}

283 0 = V_2’ = {\rm det}(\mat{y}_2’, \mat{y}_3,\mat{y}_4,\cdots,\mat{y}_D),

284\end{equation}

285this means $\mat{y}_2’$ is a linear combination of
$(\mat{y}_3,\cdots,\mat{y}_D)$, hence can be removed from the vector list.

286

287

288\begin{figure}

289 \centering

290 \includegraphics[width=0.8\linewidth]{figures/lattice-simplification.png}

291 \caption{Both red and blue basis form a minimal parallelogram (in terms of
cell volume), but one can further simplify red to blue by linear combination
(simplicity in the sense of small $\ell_2$ norm).}

292 \label{fig:lattice-simplification}

293\end{figure}

294

295{\bf Step 3: Simplification of basis vectors.} We want to further simplify
basis vectors. For example, the basis vectors obtained in step 2 may have
large norms. For example $D=2$, the standard integer lattice has $\mat{b}_1 =
(1,0)$ and $\mat{b}_2=(0,1)$, but they are infinitely many possibilities after
step 2, as long as $pt-sq=\pm 1$ for $\mat{b}_1 = (p,q)$ and
$\mat{b}_2=(s,t)$, e.g., $\mat{b}_1 = (3,5)$ and $\mat{b}_2 = (4,7)$.

296

297To minimize $\ell_2$ norms, we choose a basis and project-and-subtract for
other bases. Note that: (1) again we are only allowed to subtract integer
times of the chosen basis; (2) the volume of the parallelogram does not change
since the project-and-subtract matrix has determinant 1 (suppose $\mat{b}_i
(i=2,3,\cdots,D)$ are projected to $\mat{b}_1$ and subtracted by multiples of
$\mat{b}_1$. $p_{*}$ represents projection integers):

298

299\begin{equation}

300 \begin{pmatrix}

301 1 & p_{2\to 1} & p_{3\to 1} & \cdots & p_{D\to 1} \\\

302 0 & 1 & 0 & \cdots & 0 \\\

303 0 & 0 & 1 & \cdots & 0 \\\

304 \vdots & \vdots & \vdots & & \vdots \\\

305 0 & 0 & 0 & \cdots & 1

306 \end{pmatrix}

307\end{equation}

308

309We do this iteratively, until no norm can become shorter via project-and-
subtract. Please see Figure~\ref{fig:lattice-simplification} for an
illustration of how simplification works for a 2D example.

310

311{\bf Computation overhead} is actually surprisingly small. In typical
cases, we only need to call $O(1)$ times of GCD.

312

313{\bf Dealing with noise} Usually the integer lattice in the hidden space is
not perfect, i.e., vulnerable to noise. How do we extract integer lattices in
a robust way in the presence of noise? Note that the terminating condition for
the GCD algorithm is when the remainder is exactly zero - we relax this
condition to that the absolute value of the remainder to be smaller than a
threshold $\epsilon_{\rm gcd}$. Another issue regarding noise is that noise
can be accumulated in the GCD iterations, so we hope that GCD can converge in
a few steps. To achieve this, we select hidden states in a small region with
data fraction $p\%$ of the whole data. Since both $\epsilon_{\rm gcd}$ and $p$
depends on data and neural network training which we do not know a priori, we
choose to grid sweep $\epsilon_{\rm gcd}\in [10^{-3},1]$ and $p\in (0.1,100)$;
for each $(\epsilon_{\rm gcd},p)$, we obtain an integer lattice and compute
its description length. We select the $(\epsilon_{\rm gcd},p)$ which gives the
lattice with the smallest description length. The description length includes
two parts: integer descriptions of hidden states ${\rm log}(1+|Z|^2)$, and
residual of reconstruction ${\rm log}(1+(\frac{AZ+b-X}{\epsilon_{\rm dl}})^2)$
with $\epsilon_{\rm dl}=10^{-4}$.

314

315\section{Linear lattice finder}\label{app:linear-lattice-finder}

316

317Although our RNN can represent general nonlinear functions, in the special
case when the RNN actually performs linear functions, program synthesis can be
much easier. So if the hidden MLP is linear, we would expect the hidden states
to be an integer lattice, because inputs are integer lattices and the mappings
are linear. Effectively the hidden MLP works as a linear function:
$\h^{(t)}=W_h\h^{(t-1)}+W_i\x^{(t)}$ (we neglected the bias term since it is
not relevant to finding basis vectors of a lattice).

318

319Suppose we have input series $\x^{(1)}, \x^{(2)}, ..., \x^{(t)}$, then
$\h^{(t)}$ is

320\begin{equation}

321 \h^{(t)} = \sum_{j=1}^t W_h^{t-j}W_i\x_{j},

322\end{equation}

323Since $\x_j$ themselves are integer lattices, we could then interpret the
following as basis vectors:

324\begin{equation}

325 W_h^{t-j}W_i, j = 1,2,\cdots, t,

326\end{equation}

327which are not necessarily independent. For example, for the task of summing
up the last two numbers, $W_hW_i$ and $W_i$ are non-zero vectors and are
independent, while others $W_h^nW_i\approx 0, n\geq 2$. Then $W_hW_i$ and
$W_i$ are the two basis vectors for the lattice. In general, we measure the
norm of all the candidate basis vectors, and select the first $k$ vectors with
highest norms, which are exactly basis vectors of the hidden lattice.

328

329\section{Symbolic regression}\label{app:symbolic-regression}

330The formulation of symbolic regression is that one has data pair $(\x_i,
y_i), i=1,2,\dots,N$ with $N$ data samples. The goal is to find a symbolic
formula $f$ such that $y_i=f(\x_i)$. A function is expressed in reverse polish
notation (RPN), for example, $|a|-c$ is expressed as \texttt{aAc-} where $A$
stands for the absolute value function. We have three types of variables:

331\begin{itemize}

332 \item type-0 operator. We include input variables and constants.

333 \item type-1 operator (takes in one type-0 to produce one type-0). We
include operations $\\{>,<,\sim,H,D,A\\}$. $>$ means $+1$; $<$ means $-1$;
$\sim$ means negating the number; $D$ is dirac delta which outputs 1 only when
taking in 0; $A$ is the absolute value function;

334 \item type-2 operator (takes in two type-0 to produce on type-0). We
include operations $\\{+,*,-,\%\\}$. $+$ means addition of two numbers; $*$
means multiplication of two numbers; $-$ means subtraction of two numbers;
$\%$ is the remainder of one number module the other.

335\end{itemize}

336There are only certain types of templates (a string of numbers consisting
of 0,1,2) that are syntactically correct. For example, $002$ is correct while
$02$ is incorrect. We iterate over all the templates not longer than 6
symbols, and for each template, we try all the variable combinations. Each
variable combination corresponds to a symbolic equation $f$, for which we can
check whether $f(\x_i)=y_i$ for 100 data points. If success, we terminate the
brute force program and return the successful formula. If brute force search
does not find any correct symbolic formula within compute budget, we will
simply return the formula $a$, to make sure that the program can still be
synthesized but simply fail to make correct predictions.

337

338\section{Neural Network Normalization Algorithms}
\label{sec:hammer_details}

339It is well known that neural networks exhibit a large amount of symmetry.
That is, there are many transformations that can be applied to networks
without affecting the map $y = f(x)$ that they compute. A classic example is
to permute the neurons within layers.

340

341In this section, we describe a suite of normalizers that we use to
transform our networks into a standard form, such that the algorithms that
they learn are easier to interpret. We call our five normalizers
‘‘Whitening’’, ‘‘Jordan normal form (JNF)’’, ‘‘Toeplitz’’, ‘‘De-bias’’, and
‘‘Quantization’’.

342

343The main symmetry which we focus on is a linear transformation of the
hidden space $\h \mapsto \A\h$, which requires the following changes to $f$
and $g$:

344\begin{align*}

345 f(\h, \x) = \W\h + \V\x + \b \implies& f(\h, \x) = \A\W\A^{-1}\h + \A\V\x
+ \A\b \\\

346 g(\h) = G(\U\h + \c) \implies& f(\h) = G(\U\A^{-1}\h + \c)

347\end{align*}

348and is implemented by changing the weights:

349\begin{align*}

350 \W \implies& \A\W\A^{-1} \\\

351 \V \implies& \A\V \\\

352 \b \implies& \A\b \\\

353 \U \implies& \U\A^{-1}

354\end{align*}

355

356\def\S{\bf S}

357\def\I{\bf I}

358

359For this symmetry, we can apply an arbitrary invertible similarity
transformation $\A$ to $\W$, which is the core idea underlying our
normalizers, three of which have their own unique ways of constructing $\A$,
as we describe in the sections below. Most importantly, one of our normalizers
exploits $\A$ to convert the hidden-to-hidden transformation $\W$ into Jordan
normal form, in the case where $f$ is linear. Recent work has shown that large
recurrent networks with linear hidden-to-hidden transformations, such as state
space models \citep{gu2023mamba} can perform just as well as transformer-based
models in language modeling on a large scale. A main advantage of using linear
hidden-to-hidden transformations is the possibility of expressing the hidden
space in it’s eigenbasis. This causes the hidden-to-hidden transformation to
become diagonal, so that it can be computed more efficiently. In practice,
modern state space models assume diagonality, and go further to assume the
elements on the diagonal are real; they fix the architecture to be this way
during training.

360

361By doing this, we ignore the possibility of linear hidden-to-hidden
transformations that cannot be transformed into a real diagonal matrix via
diagonalization. Such examples include rotation matrices (whose eigenvalues
may be complex), and shift matrices (whose eigenvalues are degenerate and
whose eigenvectors are duplicated). A more general form than the diagonal form
is the Jordan normal form, which consists of Jordan blocks along the diagonal,
each of which has the form $\lambda \I + \S$ for an eigenvalue $\lambda$ and
the shift matrix $\S$ with ones on the superdiagonal and zeros elsewhere. The
diagonalization is a special case of Jordan normal form, and all matrices can
be transformed to Jordan normal form. A simple transformation can also be
applied to Jordan normal forms that contain pairs of complex generalized
eigenvectors, to convert them into real matrices.

362

363For nonlinear hidden-to-hidden transformations, we compute $\W$ as though
the nonlinearities have been removed.

364

365\subsection{Whitening Transformation}

366Similar to normalizing the means and variances of a dataset before feeding
it into a machine learning model, a good first preprocessing step is to
normalize the distribution of hidden states. We therefore choose to apply a
whitening transformation to the hidden space. To compute the transformation,
we compute the covariance matrix of hidden activations across the dataset, and
use the singular value decomposition (SVD) of this covariance matrix to find
the closest transformation to the identity that will bring this covariance
matrix to the identity. We ignore any directions with covariance less than
$\epsilon=0.1$, which cause more instability when normalized. We then post-
apply this transformation to the last linear layer of the hidden-to-hidden
transformation and its biases, and pre-apply its inverse to the first layers
of the hidden-to-hidden and hidden-to-output transformations. This leaves the
net behavior of the network unchanged. Other transformations which we use in
other normalizers operate in a similar manner, by post-applying and pre-
applying a transformation and its inverse transformation to the first and last
layers that interact with the hidden space.

367

368\subsection{Jordan Normal Form Transformation}

369Critically, the hidden-to-hidden transformations which we would like to
convert into Jordan normal form are imperfect because they are learned.
Eigenvectors belonging to each Jordan block must be identical, whereas this
will only be approximately true of the learned transformation.

370

371\def\T{\bf T}

372

373The Jordan normal form of a matrix is unstable; consider a matrix

374\begin{align*}

375 \W = \begin{pmatrix} 0 & 1 \\\ \delta & 0 \end{pmatrix}

376\end{align*}

377which, when $\delta \neq 0$, can be transformed into Jordan normal form by:

378\begin{align}

379 \begin{pmatrix} 0 & 1 \\\ \delta & 0 \end{pmatrix} =
\underbrace{\begin{pmatrix} 1 & 1 \\\ \sqrt{\delta} & -\sqrt{\delta}
\end{pmatrix}}_{\T} \begin{pmatrix} \sqrt{\delta} & 0 \\\ 0 & -\sqrt{\delta}
\end{pmatrix} \begin{pmatrix} 1 & 1 \\\ \sqrt{\delta} & -\sqrt{\delta}
\end{pmatrix}^{-1} \label{eq:worse_jnf}

380\end{align}

381but when $\delta = 0$, is transformed into Jordan normal form by:

382\begin{align}

383 \begin{pmatrix} 0 & 1 \\\ 0 & 0 \end{pmatrix} =
\underbrace{\begin{pmatrix} 1 & 0 \\\ 0 & 1 \end{pmatrix}}_{\T}
\begin{pmatrix} 0 & 1 \\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 \\\ 0 & 1
\end{pmatrix}^{-1} \label{eq:better_jnf}

384\end{align}

385As we can see, all of the matrices in the decomposition are unstable near
$\delta=0$, so the issue of error thresholding is not only numerical, but is
mathematical in nature as well.

386

387We would like to construct an algorithm which computes the Jordan normal
form with an error threshold $|\delta| < \epsilon=0.7$ within which the
algorithm will pick the transformation $\T$ from Equation
(\ref{eq:better_jnf}) instead of from Equation (\ref{eq:worse_jnf}).

388

389\def\X{{\bf X}}

390\def\J{{\bf J}}

391\def\F{{\bf F}}

392

393Our algorithm first computes the eigenvalues $\lambda_i$, and then
iteratively solves for the generalized eigenvectors which lie in
$\text{ker}((\W-\lambda \I)^k)$ for increasing $k$. The approximation occurs
whenever we compute the kernel (of unknown dimension) of a matrix $\X$; we
take the SVD of $\X$ and treat any singular vectors as part of the nullspace
if their singular values are lower than the threshold $\epsilon$, calling the
result $\epsilon\text{-ker}(\X)$.

394

395Spaces are always stored in the form of a rectangular matrix $\F$ of
orthonormal vectors, and their dimension is always the width of the matrix. We
build projections using $\text{proj}(\F) = \F\F^H$, where $\F^H$ denotes the
conjugate transpose of $\F$. We compute kernels $\text{ker}(\X)$ of known
dimension of matrices $\X$ by taking the SVD $\X=\V_1S\V_2^H$ and taking the
last singular vectors in $\V_2^H$. We compute column spaces of projectors of
known dimension by taking the top singular vectors of the SVD.

396

397The steps in our algorithm are as follows:

398\begin{enumerate}

399 \item Solve for the eigenvalues $\lambda_i$ of $\W$, and check that
eigenvalues that are within $\epsilon$ of each other form groups, ie. that
$|\lambda_i-\lambda_j|\leq\epsilon$ and $|\lambda_j-\lambda_k|\leq\epsilon$
always implies $|\lambda_k-\lambda_i|\leq\epsilon$. Compute the mean
eigenvalue for every group.

400 \item Solve for the approximate kernels of $\W-\lambda \I$ for each mean
eigenvalue $\lambda$. We will denote this operation by
$\epsilon\text{-ker}(\W-\lambda \I)$. We represent these kernels by storing
the singular vectors whose singular values are lower than $\epsilon$. Also,
construct a ‘‘corrected matrix’’ of $\W-\lambda \I$ for every $\lambda$ by
taking the SVD, discarding the low singular values, and multiplying the pruned
decomposition back together again.

401 \item Solve for successive spaces $\F_k$ of generalized eigenvectors at
increasing depths $k$ along the set of Jordan chains with eigenvalue
$\lambda$, for all $\lambda$. In other words, find chains of mutually
orthogonal vectors which are mapped to zero after exactly $k$ applications of
the map $\W-\lambda \I$. We first solve for $\F_0 = \text{ker}(\W-\lambda
\I)$. Then for $k>0$, we first solve for
$\J_k=\epsilon\text{-ker}((I-\text{proj}(\F_{k-1}))(\W-\lambda \I))$ and
deduce the number of chains which reach depth $k$ from the dimension of
$\J_k$, and then solve for $\F_k = \text{col}(\text{proj}(\J_k) -
\text{proj}(\F_0))$.

402 \item Perform a consistency check to verify that the dimensions of $\F_k$
always stay the same or decrease with $k$. Go through the spaces $\F_k$ in
reverse order, and whenever the dimension of $\F_k$ decreases, figure out
which direction(s) are not mapped to by applying $\W-\lambda \I$ to
$\F_{k+1}$. Do this by building a projector $\J$ from mapping vectors
representing $\F_{k+1}$ through $\W-\lambda \I$, and taking
$\text{col}(\text{proj}(\F_k)-\J)$. Solve for the Jordan chain by repeatedly
applying $\text{proj}(\F_i)(\W_i-\lambda \I)$ for $i$ starting from $k-1$ and
going all the way down to zero.

403 \item Concatenate all the Jordan chains together to form the
transformation matrix $\T$.

404\end{enumerate}

405

406The transformation $\T$ consists of generalized eigenvectors which need not
be completely real but may also include pairs of generalized eigenvectors that
are complex conjugates of each other. Since we do not want the weights of our
normalized network to be complex, we also apply a unitary transformation which
changes any pair of complex generalized eigenvectors into a pair of real
vectors, and the resulting block of $\W$ into a multiple of a rotation matrix.
As an example, for a real 2 by 2 matrix $\W$ with complex eigenvectors, we
have

407\begin{align*}

408\W &= \T\begin{pmatrix} a + bi & 0 \\\ 0 & a - bi \end{pmatrix}\T^{-1} \\\

409&= \T\T’\begin{pmatrix} a & -b \\\ b & a \end{pmatrix}(\T\T’)^{-1}, \quad
\T’ = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & i \\\ 1 & -i \end{pmatrix}

410\end{align*}

411

412\subsection{Toeplitz Transformation}

413Once $\W$ is in Jordan normal form, each Jordan block is an upper
triangular Toeplitz matrix. Upper-triangular Toeplitz matrices, including
Jordan blocks, will always commute with each other, because they are all
polynomials of the shift matrix (which has ones on the superdiagonal and zeros
elsewhere,) and therefore these transformations will leave $\W$ unchanged, but
will still affect $\V$. We split $\V$ up into parts operated on by each Jordan
block, and use these Toeplitz transformations to reduce the most numerically
stable columns of each block of $\V$ to one-hot vectors. The numerically
stability of a column vector is determined by the absolute value of the bottom
element of that column vector, since it’s inverse will become the degenerate
eigenvalues of the resulting Toeplitz matrix. If no column has a numerically
stability above $\epsilon=0.0001$, we pick the identity matrix for our
Toeplitz transformation.

414

415\subsection{De-biasing Transformation}

416Oftentimes, $\W$ is not full rank, and has a nontrivial nullspace. The bias
$\b$ will have some component in the direction of this nullspace, and
eliminating this component only affects the behavior of the output network
$g$, and the perturabtion cannot carry on to the remainder of the sequence via
$f$. Therefore, we eliminate any such component, and compensate accordingly by
modifying the bias in the first affine layer of $g$. We identify the
nullspaces by taking an SVD and identifying components whose singular value is
less than $\epsilon=0.1$.

417

418\subsection{Quantization Transformation}

419After applying all of the previous transformations to the RNN, it is common
for many of the weights to become close to zero or some other small integer.
Treating this as a sign that the network is attempting to implement discrete
operations using integers, we snap any weights and biases that are within a
threshold $\epsilon=0.01$ of an integer, to that integer. For certain simple
tasks, sometimes this allows the entire network to become quantized.

420

421\section{Supplementary training data details}
\label{extra_task_explanation}

422

423\def\v{{\bf v}}

424\def\F{{\bf F}}

425

426Here we present additional details on the benchmark tasks marked "see text"
in Table \ref{tab:tasks}:

427\begin{itemize}

428 \item \textbf{Div\\_3/5/7:} This is a long division task for binary
numbers. The input is a binary number, and the output is that binary number
divided by 3, 5, or 7, respectively. The remainder is discarded. For example,
we have 1000011/11=0010110 (67/3=22). The most significant bits occur first in
the sequence.

429 \item \textbf{Dithering:} This is a basic image color quantization task,
for 1D images. We map 4-bit images to 1-bit images such that the cumulative
sum of pixel brightnesses of both the original and dithered images remains as
close as possible.

430 \item \textbf{Newton\\_Gravity:} This is an euler forward propagation
technique which follows the equation $F = \text{\textit{input}} - 1, v \mapsto
v + F, x \mapsto x + v$.

431 \item \textbf{Newton\\_Spring:} This is an euler forward propagation
technique which follows the equation $F = \text{\textit{input}} - x, v \mapsto
v + F, x \mapsto x + v$.

432 \item \textbf{Newton\\_Magnetic:} This is an euler forward propagation
technique which follows the equation $F_x = \text{\textit{input}}_1 - v_y, F_y
= \text{\textit{input}}_2 + v_x, \v \mapsto \v + \F, \x \mapsto \x + \v$.

433\end{itemize}

434

435% Used majority, max, min to be solvable with ReLU activations.

436

437\section{Generated programs}\label{app:generated-programs}

438

439

440\begin{comment}

441

442

443\end{comment}

444

445

446\definecolor{codegreen}{rgb}{0,0.6,0}

447\definecolor{codegray}{rgb}{0.5,0.5,0.5}

448\definecolor{codepurple}{rgb}{0.58,0,0.82}

449\definecolor{backcolour}{rgb}{0.95,0.95,0.92}

450

451\lstdefinestyle{mystyle}{

452 backgroundcolor=\color{backcolour},

453 commentstyle=\color{codegreen},

454 keywordstyle=\color{magenta},

455 numberstyle=\tiny\color{codegray},

456 stringstyle=\color{codepurple},

457 basicstyle=\ttfamily\footnotesize,

458 breakatwhitespace=false,

459 breaklines=true,

460 captionpos=b,

461 keepspaces=true,

462 numbers=left,

463 numbersep=5pt,

464 showspaces=false,

465 showstringspaces=false,

466 showtabs=false,

467 tabsize=2

468}

469

470\lstset{style=mystyle}

471

472This section includes all successfully generated Python programs.

473

474\newcount\tmpnum

475\def\storedata#1#2{\tmpnum=0 \edef\tmp{\string#1}\storedataA#2\end}

476\def\storedataA#1{\advance\tmpnum by1

477 \ifx\end#1\else

478 \expandafter\def\csname data:\tmp:\the\tmpnum\endcsname{#1}%

479 \expandafter\storedataA\fi

480}

481\def\getdata[#1]#2{\csname data:\string#2:#1\endcsname}

482

483

484%% define tasks in \mydata %%

485\storedata\mydata{

486{Binary-Addition}

487{Bitwise-Xor}

488{Bitwise-Or}

489{Bitwise-And}

490{Bitwise-Not}

491{Parity-Last2}

492{Parity-Last3}

493{Parity-All}

494{Parity-Zeros}

495{Sum-All}

496{Sum-Last2}

497{Sum-Last3}

498{Sum-Last4}

499{Sum-Last5}

500{Sum-Last6}

501{Sum-Last7}

502{Current-Number}

503{Prev1}

504{Prev2}

505{Prev3}

506{Prev4}

507{Prev5}

508{Previous-Equals-Current}

509{Diff-Last2}

510{Abs-Diff}

511{Abs-Current}

512{Bit-Shift-Right}

513{Bit-Dot-Prod-Mod2}

514{Add-Mod-3}

515{Newton-Freebody}

516{Newton-Gravity}

517{Newton-Spring}

518{Dafny-Code}}

519

520

521\begin{multicols}{2}

522\noindent

523\input{./programs/control_program_input.tex}

524\end{multicols}

525

526% \input{./programs/control_program_input.tex}

527

528

529

530\subsection{Formal Verification}\label{app:dafnyverification}

531

532The Dafny programming language is designed so that programs can be formally
verified for correctness. The desired behavior of a program can be explicitly
specified via preconditions, postconditions, and invariants, which are
verified via automated theorem proving. These capabilities make Dafny useful
in fields where correctness and safety are crucial.

533

534We leverage Dafny’s robust verification capabilities to prove the
correctness of the bit addition Python program synthesized by MIPS. The bit
addition Python program was first converted to Dafny, then annotated with
specific assertions, preconditions, and postconditions that defined the
expected behavior of the code. Each annotation in the code was then formally
verified by Dafny, ensuring that under all possible valid inputs, the code’s
output would be consistent with the expected behavior. On line 79, we show
that the algorithm found by MIPS is indeed equivalent to performing bit
addition with length 10 bitvectors in Dafny.

535

536\input{./programs/dafny.tex}

537

538%\end{comment}

539

540

541\end{document}’


authorpersonAndres J. Ramirez, personBetty
H. C. Cheng, personPhilip K. McKinley, and
personBenjamin E. Beckmann. year2010.
Automatically generating adaptive logic to balance
non-functional tradeoffs during reconfiguration. In
booktitleProceedings of the 7th International Conference on
Autonomic Computing, ICAC 2010, Washington, DC, USA, June 7-11, 2010,
editorpersonManish Parashar, personRenato
J. O. Figueiredo, and personEmre Kiciman (Eds.).
publisherACM, pages225–234.

[Ramirez, Knoester, Cheng, and
McKinleyRamirez et al2009]
authorpersonAndres J. Ramirez,
personDavid B. Knoester, personBetty H. C. Cheng,
and personPhilip K. McKinley. year2009.
Applying genetic algorithms to decision making in
autonomic computing systems. In booktitleProceedings of the
6th International Conference on Autonomic Computing, ICAC 2009, June 15-19,
2009. pages97–106.

[Sayyad and AmmarSayyad and Ammar2013]
authorpersonAbdel Salam Sayyad and
personHany Ammar. year2013.
Pareto-optimal search-based software engineering
(POSBSE): A literature survey. In booktitleThe 2nd
International Workshop on Realizing Artificial Intelligence Synergies in
Software Engineering (RAISE). IEEE, pages21–27.

[Sayyad, Ingram, Menzies, and AmmarSayyad
et al2013a]
authorpersonAbdel Salam Sayyad, personJoseph
Ingram, personTim Menzies, and personHany Ammar.
Optimum feature selection in software product
lines: Let your model and values guide your search. In
booktitleInternational Workshop on Combining Modelling and
Search-Based Software Engineering. pages22–27.

[Sayyad, Ingram, Menzies, and AmmarSayyad
et al2013b]
authorpersonAbdel Salam Sayyad, personJoseph
Ingram, personTim Menzies, and personHany Ammar.
Scalable product line configuration: A straw to
break the camel's back. In booktitleIEEE/ACM International
Conference on Automated Software Engineering. pages465–474.

[Sayyad, Menzies, and AmmarSayyad
et al2013c]
authorpersonAbdel Salam Sayyad, personTim
Menzies, and personHany Ammar.
On the value of user preferences in search-based
software engineering: A case study in software product lines. In
booktitleInternational Conference on Software Engineering.

[Shahbazian, Karthik, Brun, and
MedvidovicShahbazian et al2020]
authorpersonArman Shahbazian, personSuhrid
Karthik, personYuriy Brun, and personNenad
Medvidovic. year2020.
eQual: informing early design decisions. In
booktitleESEC/FSE '20: 28th ACM Joint European Software
Engineering Conference and Symposium on the Foundations of Software
Engineering, Virtual Event, USA, November 8-13, 2020,
editorpersonPrem Devanbu, personMyra B.
Cohen, and personThomas Zimmermann (Eds.).
publisherACM, pages1039–1051.

[Sobhy, Minku, Bahsoon, Chen, and KazmanSobhy
et al2020]
authorpersonDalia Sobhy, personLeandro L.
Minku, personRami Bahsoon, personTao Chen, and
personRick Kazman. year2020.
Run-time evaluation of architectures: A case
study of diversification in IoT.
journalJournal of Systems and Software
volume159 (year2020).

[Staats, Gay, Whalen, and HeimdahlStaats
et al2012]
authorpersonMatt Staats, personGregory Gay,
personMichael W. Whalen, and personMats Per Erik
Heimdahl. year2012.
On the Danger of Coverage Directed Test Case
Generation. In booktitleFundamental Approaches to Software
Engineering - 15th International Conference, FASE 2012, Held as Part of the
European Joint Conferences on Theory and Practice of Software, ETAPS 2012,
Tallinn, Estonia, March 24 - April 1, 2012. Proceedings
(seriesLecture Notes in Computer Science,
Vol. volume7212), editorpersonJuan
de Lara and personAndrea Zisman (Eds.).
publisherSpringer, pages409–424.

[Vargha and DelaneyVargha and
authorpersonAndrás Vargha and
personHarold D. Delaney. year2000.
A Critique and Improvement of the CL Common
Language Effect Size Statistics of McGraw and Wong.

[Wada, Suzuki, Yamano, and ObaWada
et al2012]
authorpersonHiroshi Wada, personJunichi
Suzuki, personYuji Yamano, and personKatsuya Oba.
E3: A Multiobjective Optimization Framework for
SLA-Aware Service Composition.
journalIEEE Transactions on Services Computing
volume5, number3 (year2012),

[Wagner, Klein, Klopper, Ishikawa, and
HonidenWagner et al2012]
authorpersonFlorian Wagner, personAdrian
Klein, personBenjamin Klopper, personFuyuki
Ishikawa, and personShinichi Honiden.
Multi-objective Service Composition with Time- and
Input-Dependent QoS. In booktitleIEEE International
Conference on Web Services. pages234–241.

[Wagner, Beume, and NaujoksWagner
et al2007]
authorpersonTobias Wagner, personNicola
Beume, and personBoris Naujoks.
Pareto-, Aggregation-, and Indicator-Based Methods
in Many-Objective Optimization.
In booktitleProceedings of the 4th International
Conference on Evolutionary Multi-Criterion Optimization (EMO).

[Wang, Lin, and TangWang
et al2012]
authorpersonKewen Wang, personXuelian Lin,
and personWenzhong Tang. year2012.
Predator - An experience guided configuration
optimizer for Hadoop MapReduce. In booktitle4th IEEE
International Conference on Cloud Computing Technology and Science
Proceedings, CloudCom 2012, Taipei, Taiwan, December 3-6, 2012.
publisherIEEE Computer Society, pages419–426.

[Wang, Ali, Yue, and LiaaenWang
et al2018a]
authorpersonShuai Wang, personShaukat Ali,
personTao Yue, and personMarius Liaaen.
Integrating Weight Assignment Strategies With
NSGA-II for Supporting User Preference Multiobjective Optimization.
journalIEEE Trans. Evol. Comput.
volume22, number3 (year2018),

[Wang, Ong, Sun, Gupta, and ZhangWang
et al2018b]
authorpersonZhenkun Wang, personYew-Soon
Ong, personJianyong Sun, personAbhishek Gupta, and
personQingfu Zhang. year2018b.
A generator for multiobjective test problems with
difficult-to-approximate Pareto front boundaries.
journalIEEE Transactions on Evolutionary
Computation volume23, number4
(year2018), pages556–571.

authorpersonFrank Wilcoxon.
Individual Comparisons by Ranking Methods.

[Xia, Krishna, Chen, Mathew, Shen, and
MenziesXia et al2018]
authorpersonTianpei Xia, personRahul
Krishna, personJianfeng Chen, personGeorge Mathew,
personXipeng Shen, and personTim Menzies.
Hyperparameter Optimization for Effort Estimation.
journalCoRR  volumeabs/1805.00336

[Xue and LiXue and Li2020]
authorpersonYinxing Xue and personYan-Fu
Li. year2020.
Multi-Objective Integer Programming Approaches for
Solving the Multi-Criteria Test-Suite Minimization Problem: Towards Sound and
Complete Solutions of a Particular Search-Based Software-Engineering
journalACM Trans. Softw. Eng. Methodol.
volume29, number3 (year2020).

[Yang, Li, Liu, and ZhengYang
et al2013]
authorpersonShengxiang Yang, personMiqing
Li, personXiaohui Liu, and personJinhua Zheng.
A grid-based evolutionary algorithm for
many-objective optimization.
journalIEEE Transactions on Evolutionary
Computation volume17, number5
(year2013), pages721–736.

[Zhang and LiZhang and Li2007]
authorpersonQingfu Zhang and personHui
Li. year2007.
MOEA/D: A Multiobjective Evolutionary Algorithm
Based on Decomposition.
journalIEEE Trans. Evol. Comput.
volume11, number6 (year2007),

[Zhang, Harman, and MansouriZhang
et al2007]
authorpersonYuanyuan Zhang, personMark
Harman, and personS. Afshin Mansouri.
The multi-objective next release problem. In
booktitleProceedings of the Genetic and Evolutionary
Computation Conference. pages1129–1137.

[Zhang, Harman, Ochoa, Ruhe, and
BrinkkemperZhang et al2018]
authorpersonYuanyuan Zhang, personMark
Harman, personGabriela Ochoa, personGuenther Ruhe,
and personSjaak Brinkkemper. year2018.
An Empirical Study of Meta- and Hyper-Heuristic
Search for Multi-Objective Release Planning.
journalACM Trans. Softw. Eng. Methodol.
volume27, number1 (year2018),

[Zheng, Zhang, and LyuZheng
et al2012]
authorpersonZibin Zheng, personYilei Zhang,
and personMichael R Lyu. year2012.
Investigating QoS of real-world web services.
journalIEEE transactions on services computing
volume7, number1 (year2012),

[Zitzler and KünzliZitzler and
authorpersonEckart Zitzler and personSimon
Künzli. year2004.
Indicator-Based Selection in Multiobjective
Search. In booktitleParallel Problem Solving from Nature -
PPSN VIII, 8th International Conference, Birmingham, UK, September 18-22,
2004, Proceedings (seriesLecture Notes in Computer
Science, Vol. volume3242),
editorpersonXin Yao, personEdmund K.
Burke, personJosé Antonio Lozano, personJim
Smith, personJuan Julián Merelo Guervós,
personJohn A. Bullinaria, personJonathan E. Rowe,
personPeter Tiño, personAta Kabán, and
personHans-Paul Schwefel (Eds.).
publisherSpringer, pages832–842.

[Zitzler and ThieleZitzler and
authorpersonEckart Zitzler and
personLothar Thiele. year1998.
Multiobjective Optimization Using Evolutionary
Algorithms - A Comparative Case Study. In
booktitleParallel Problem Solving from Nature - PPSN V,
5th International Conference, Amsterdam, The Netherlands, September 27-30,
1998, Proceedings (seriesLecture Notes in Computer
Science, Vol. volume1498),
editorpersonA. E. Eiben, personThomas
Bäck, personMarc Schoenauer, and
personHans-Paul Schwefel (Eds.).
publisherSpringer, pages292–304.