Break It Down:  Evidence for Structural Compositionality in Neural Networks
Authors: Michael A. Lepori
Thomas Serre
Ellie Pavlick
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Deep Learning
Compositionality
Cognitive Science

Abstract: Though modern neural networks have achieved impressive performance in both vision and language tasks, we know little about the functions that they implement. One possibility is that neural networks implicitly break down complex tasks into subroutines, implement modular solutions to these subroutines, and compose them into an overall solution to a task --- a property we term structural compositionality.  Another possibility is that they may simply learn to match new inputs to learned templates, eliding task decomposition entirely. Here, we leverage model pruning techniques to investigate this question in both vision and language across a variety of architectures, tasks, and pretraining regimens. Our results demonstrate that models oftentimes implement solutions to subroutines via modular subnetworks, which can be ablated while maintaining the functionality of other subnetworks. This suggests that neural networks may be able to learn compositionality, obviating the need for specialized symbolic mechanisms.

Break It Down: Evidence for Structural Compositionality in Neural Networks
Michael A. Lepori Thomas Serre
Ellie Pavlick'
Department of Computer Science
*Carney Institute for Brain Science
Brown University
Abstract
Though modern neural networks have achieved impressive performance in both vision and language tasks, we know little about the functions that they implement. One possibility is that neural networks implicitly break down complex tasks into subroutines, implement modular solutions these subroutines, and compose them into an overall solution to a task - a property we term structural compositionality Another possibility is that they may simply learn to match new inputs to learned templates, eliding task decomposition entirely. Here, we leverage model pruning techniques to investigate this question in both vision and language across variety of architectures, tasks, and pretraining regimens. Our results demonstrate that models often implement solutions to subroutines via modular subnetworks, which can be ablated while maintaining the functionality of other subnetworks. This suggests that neural networks may be able to learn compositionality, obviating the need for specialized symbolic mechanisms.
Introduction
Though neural networks have come to dominate most subfields AI, much remains unknown about the functions that they learn to implement. In particular, there is debate over the role of compositionality. Compositionality has long been touted as a key property of human cognition, enabling humans to exhibit flexible and abstract language processing and visual processing, among other cognitive processes (Marcus 2003) Piantadosi et al., 2016 Lake et al. 2017 Smolensky et al. 2022). According to common detinitions QQuilty-Dunn Dunn al. 2022 Fodor & Lepore (002), representational system is compositional if it implements a set of discrete constituent functions that exhibit some degree of modularity. That is, blue circle is represented compositionally if system is able to entertain the concept blue independently of circle, and vice-versa.
It is an open question whether neural networks require explicit symbolic mechanisms to implement compositional solutions, or whether they implicitly learn to implement compositional solutions during training. Historically, artificial neural networks have been considered non-compositional systems, instead solving tasks by matching new inputs to learned templates (Mareus 2003 Quilty- et al. 2022). Neural networks' apparent lack of compositionality has served key point in favor of integrating explicit symbolic mechanisms into contemporary artificial intelligence systems (Andreas)
al. 2016 Koh al. 2020 Ellis et al. 2023 Lake et al, 2017). However, modern neural networks, with no explicit inductive bias towards compositionality have demonstrated successes on increasingly complex tasks. This raises the question: these models succeeding by implementing compositional
solutions under the hood (Mandelbaum et al., 2022)
"Conrespondence to: mi chael chaeheeepporreeeee perporr@brown...m edu
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Contributions and Novelty:
We introduce the concept of structural compositionality, which characterizes the extent to which neural networks decompose compositional tasks into subroutines and implement them modularly. We test for structural compositionality in several different models across both language and visior
2. We discover that, surprisingly, there is substantial evidence that many models implement subroutines in modular subnetworks, though most not exhibit perfect task decomposition.
3. We characterize the effect of unsupervised pretraining structural compositionality in fine-tuned networks and find that pretraining leads to a more consistently compositional structure in language models.
This study contributes to the emerging body of work on "mechanistic interpretability" (Olah 2022
Cammarata et al. 2020; Ganguli et al. 202T; Henighan et al. (023) which seeks to explain the algorithms that neural networks implicitly implement within their weights. We make use of techniques from model pruning in order to gain insight into these algorithms. While earlier versions of these techniques have been applied to study modularity in multitask setting (Csordás et al. 2021). our work novel in that it applies the method to more complex language and vision models, studies more complex compositional tasks, and connects the results to a broader discussion about defining and measuring compositionality within neural networks.
2 Structural Compositionality
Most prior work on compositionality in neural networks has focused on whether they generalize in accordance with the compositional properties of data (Etinger et al., 2018: Kim & Linzen 2020 Hupkes et al. 2020 Such work has mostly yielded negative results i.c., evidence that neural networks fail to generalize compositionally. This work is important for understanding how current models will behave in practice. However, generalization studies alone permit only limited conclusions about how models work.
As discussed above, leading definitions of compositionality are defined in terms of system's 's representations, not its behavior. That is, definitions contrast compositional systems (which implement modular constituents) with noncompositional systems (which might, e.g., rely on learned templates). Poor performance on generalization studies does not differentiate these two types of systems, since even a definitionally compositional system might fail at these generalization tasks. For example, Bayesian network that explicitly represents and composes distinct shape and color properties might nonetheless classify a blue circle as red circle if it has low prior for predicting the color blue and high prior for predicting the color red.
Thus, in this work, focus on evaluating the extent to which model's 's representations are structured compositionally. Consider the task described in Figure T In this task, a network learns to select the "odd-one-out" among four images. Three of them follow a compositional rule (they all contain two shapes, one of which is inside and in contact with the other). One of them breaks this rule, There least ways that a network might learn solve this type of compositional task. (1) A network might compare new inputs to prototypes or iconic representations of previously-seen inputs, avoiding any decomposition of these prototypes into constituent parts (i.c., might implement non-compositional solution). (2) A network might implicitly break the task down into subroutines, implement solutions each, and compose these results into a solution (i.e., it might implement compositional solution). In this case, the subroutines consist of a (+/- Inside) detector and (+/- Contact) detector.
If a model trained on this task exhibits structural compositionallit, then we would expect to find a subnetwork that implements each subroutine within the parameters of that model. This subnetwork should compute one subroutine, and not the other (Figure [ Bottom Right; "Subnetwork") "), and it should be modular with respect to the rest of the network it should be possible to ablate this subnetwork, harming the model's 's ability to compute one subroutine while leaving the other subroutine largely intact (Figure I Bottom Right; "Ablation"), However, if model does not exhibit structural compositionality, then it has only learned the conjunction of the subroutines rather than
Our code is publicly available at http:s///ggtttooooooo//////////p Subbetworkk

---

Task
Non- Compositonal Solution
Compos ponaa Solution
Contact (+)
Contast Inside (+)
Inside (+)
Class
Contact
Contact
Centact
Contact
Contact (+)
Inside
Imaide
X
Traedd"" Sucnctwerg
Subnobwork
Subnetwork Ablation
Subnetwork Ablation
Figure 1: (Left) An illustration of the tasks used study structural compositionality. Stimuli generated via the composition of two subroutines: (+/- Inside) and (+/- Contact). These stimuli are used construct odd-one-out tasks, where the model tasked with identifying the image that does not follow rule from set of four samples. Here, two objects must be in contact, and one must be inside the other. Rule following images correspond the upper right quadrant. model may solve this task in two ways. (Middle) It may implement learned template that encodes only the conjunction of the two subroutines. In this case, one should not be able to find subnetwork that implements one subroutine and does not implement the other. Concretely, there should be no difference in the subnetwork's 's performance on examples that depend on computing one subroutine vs. another. Ablating this subnetwork should harm the computation of both subroutines equally. In other words, there should be no difference accuracy between examples that depend on different subroutines. (Right) A model may implement compositional solution, which computes each subroutine in modular subnetworks and combines them. In this case, one should find subnetwork that implements, say, (+/- Inside), and this subnetwork should achieve high accuracy on examples that require computing (+/- Inside) and low performance on examples that require computing (+/- Contact). In other words, the difference in accuracies between the (+/- Inside) and (+/- Contact) examples should be positive. Likewise, one should be able to ablate this subnetwork and maintain performance on (+/- Contact) while compromising performance on (+/- Inside), and so the difference in performance should be negative. Hypothetical results are represented differences in performance between both types of examples.
non-compositional solution, e.g., storing
their composition. should not be possible to find a subnetwork that implements one subroutine and not the other, and ablating subnetwork should hurt accuracy both subroutines equally (Figure Bottom Center). This definition related to prior work on modularity in neural networks (Csordás al. 2021 Hod et al. 2022), but here specifically focus modular representations of compositional tasks.
3 Experimental Design
3.1 Preliminaries
Here we define terms used in the rest of the paper. Subroutine: A binary rule. The 4th subroutine denoted SR,, Compositional Rule: A binary rule that maps input to output according to C' SR, &:SR2, where SR; is subroutine. Compositional rules are denoted C. Base Model: A model that is trained to solve a task defined by compositional rule. Denoted Mc. Subnetwork: subset of the parameters of base model, which implements one subroutine. The subnetwork that implements SR, is denoted Sub, This implemented as binary mask, m,, over the parameters of the base model, 8, such that Sub; Mc where @ refers to elementwise multiplication.
3

---

A) Train Bose Model
Teain Inside Contact
+
B| Find Bubroutine Subnetwork
Train Inside va. Outsido
Test Target SR
Test Other BR
Papect
Target SiR
Expest Fallure
Expect Success
Figure 2: Illustration of the experimental design. For brevity, we denote "subroutine" as SR in the diagram. (A) First, we train neural network on compositional task that it can achieve high accuracy on the task. (B) We then optimize a binary mask over weights, such that the resulting subnetwork can compute one subroutine (+/- Inside) while ignoring the other (+/- Contact). We evaluate this subnetwork on datasets that require computing the target subroutine (+/- Inside). We also evaluate this subnetwork on datasets that require computing the other subroutine (+/- Contact). We expect success on the first evaluation and failure on the second if the model exhibits structural compositionality. (C) We invert the binary mask learned in (B), ablating the subnetwork. We evaluate this on the same two datasets, expecting performance to be harmed on the target subroutine and performance to be high for the other subroutine.
ensuring
Ablated Model:
The complement set of parameters of particular subnetwork. After ablating Sub, we denote the ablated model Mattater
3.2 Experimental Logic
Consider a compositional rule, C, such as the "Inside-Contact" rule described in Figures | and The rule is composed of subroutines, SR, (+/- Inside) and SR2 (+/- Contact). We define odd-one-out task on C, as described in Section 2 See Figure three demonstrative examples using the "Inside-Contact" compositional rule. For given architecture and compositional rule, C. we train a base model, Mc. such that Mc solves the odd-one-out task to greater than 90% accuracy (Figure 2 Panel A). We wish to characterize the extent which Mc exhibits structural compositionality. Does Mc learn only the conjunction (effectively entangling the two subroutines), or does Mc implement SR, and S SR, in modular subnetworks?
"This threshold was selected arbitrarily, but our results do not depend on it. All models end up achieving 99% accuracy (See Appendix A).

---

To investigate this question, we will learn a binary mask m, over the weights 8 of Mc for each SR, resulting subnetwork Sub, Without loss generality, assume Sub, computes (+/- Inside) and Suby computes (+/- Contact), and consider investigating Sub,. We can evaluate this subnetwork on two partitions of the training set: (1) Test Target Subroutine Cases where a model must compute the target subroutine to determine the odd-one-out (e.g., cases where image exhibits Inside, + Contact)) and (2) Test Other Subroutine Cases where a model must compute the other subroutine to determine the odd-one-out (e.g., cases where the odd-one-out exhibits (+ Inside, Contact))
Following prior work (Csordás et al. 2021), we assess structural compositionality based on the sub- network's 's performance on these datasets, as well as the base model's performance after ablating the subnetwork If Mc exhibits structural compositionality. then Sub, should only be able to compute the target subroutine (+/- Inside), and thus it should perform better on Test Target Subroutine than on Test Other Subroutine. If Mc entangles the subroutines, then Suby will implement both subroutines and will perform equally on both partitions. See Figure Panel
To determine modularity, we ablate the Suby from the base model and observe the behavior of the resulting model, Matlater If Mc exhibits structural compositionality, we expect the two subroutines to be modular, such that ablating Sub, has more impact on Mablate, 's ability to compute (+/- Inside) than (+/- Contact). Thus, we would expect Mablate, to perform better on Test Other Subroutine than Test Target Subroutine. See Figure 2 Panel C. However, if Mc implemented a non con-coppoiiiionll solution, then ablating Sub, should hurt performance on both partitions equally, as the two subroutines are entangled. Thus, performance both partitions would be approximately equal.
Expected Results: For each model and task, our main results are the differences in performance between Test Target Subroutine and Test Other Subroutine for each subnetwork and ablated model. If model exhibits structural compositionality, we expect the subnetwork to produce positive difference in performance (Test Target Subroutine > Test Other Subroutine), and the corresponding ablated model produce negative difference in performance. Otherwise, we expect no differences in performance. See Figure 1 for hypothetical results.
4 Discovering Subnetworks
Consider frozen model Mo(: w) trained on an odd-one-out task defined using the compositional rule C. Within the weights of this model, we wish to discover a subnetwork that implements $ SR We further require that the discovered subnetwork should be small as possible, such that if the model exhibits structural compositionality, it can be ablated with little damage to the remainder of the network. Thus, we wish learn binary mask over the weights of trained neural network while employing Lo regularization
Most prior work that relies on learning binary masks network parameters (Coo et al. 202 Csordás et al. 2021 (Zhang et al. [202]] Guo et al.] 2021 De Cao et al. 2020 relies on stochastic approaches, introduced in Louizos al. (2018). Savarese et al. (2020) introduced continuous sparsification as a deterministic alternative to these stochastic approaches and demonstrated that it achieves superior pruning performance, both in terms of sparsity and subnetwork performance. Thus, we use continuous sparsification to discover subnetworks within our models. See Appendix B for details.
Vision Experiments
We extend the collection of datasets introduced in Zerroug et al. (2022). generating several tightly controlled datasets that implement compositions of the following subroutines: contact, inside, and number. From these three basic subroutines, we define three compositional rules: Inside- Contact, Number-Contact, and Inside-Number. We will describe the Inside-Contar tasks in detail, as the same principles apply to the other two compositional rules (See Appendix E). This
Tasks:
"This similar to Csordás et al. (2021)* PSpecialize metric.
'Over all networks, only mask weight parameters, leaving bias parameters untouched.
5

---

Figure 3: Three Inside-Contact stimuli. The odd-one-out ut always the bottom-right image in these examples. (Right) An example from the task used to train the base model. (Middle) An example from the task used to discover the +/- Inside Subroutine. (Left) An example from the task used to discover the +/- Contact Subroutine.
task contains four types of images, each containing two shapes. In these images, one shape is either inside and in contact with the other (+ Inside, + Contact), not inside of but in contact with the other Inside, Contact), inside of but not in contact with the other (+ Inside, Contact), or neither (- Inside, Contact). An example is defined as a collection of four images, three of which follow a rule and one of which does not. We train our base model predict the odd-one-out on task defined by a compositional rule over contact and inside: images of the type (+ Inside, + Contact) follow the rule, and any other image type considered the odd-one-out. See F (Left).
In order to discover a subnetwork that implements each subroutine, we define one odd-one-out task per subroutine. To discover the +/- Inside Subroutine, define (+ Inside) to be fule-following (irrespective of contact) and (- Inside) to be the odd-one-out. Similarly for the +/- Contact Subroutine. See Figure (Middle and Right, respectively). The base model has only seen data where (+ Inside, + Contact) images are rule-following. In order to align our evaluations with the base model's training data, create more datasets that probe each subroutine. For both, all rule-following images are (+ Inside, + Contact). To probe for (+/- Inside), the odd-onc-out for one dataset is always Inside, + Contact) image. This dataset is Test Target Subroutine, with respect to the subnetwork that implements (+/- Inside). Similarly, to probe for (+/- Contact), the odd-one-out is always (+ Inside, Contact) image. This dataset Test Other Subroutine, with respect to the subnetwork that implements (+/- Inside).
Our models consist of a backbone followed by 2-layer MLF which produces em- beddings of each of the four images in an example. Following Zerroug al. (2022) we compute the dot product between each of the four embeddings to produce pairwise similarity metric. The least similar embedding is predicted be the "odd-one-out". We use cross-entropy loss over the four images. During mask training, we use Ln regularization to encourage sparsity. We investigate 3 backbone architectures: Resnet50 He et al. 2016)), Wide Resnet50 Zagoruyko & Komodakis 2016), and ViT (Dosovitskiy et al., 2020). We perform hyperparameter search over batch size and learning rate to find settings that allow each model to achieve near-perfect performance. We then train 3 models with different random seeds in order probe for structural compositionality" [
Methods:
After training our base models, Mc. we perform a hyperparameter search over continuous sparsifi- cation parameters for each subroutine (See Appendix C). One hyperparameter to note is the mask configuration: the layer of the network which start masking. After finding the best continuous sparsification parameters, we run the algorithm three times per model, per subroutine, and evaluate on
'Hidden Size: 2048, Output Size: 128
"We replace all BatchNorm layers with InstanceNorm layers. BatchNorm statistics learned during training the base model do not apply to the subnetworks, and because the batch statistics vary across the different data partitions that we evaluate on.
All models trained using the Adam optimizer (Kingma & Ba 2014 with early stopping for maximum of 100 epochs (patience set to epochs). We evaluate using a held out validation set after every epoch and take the model that minimizes loss on the validation set. We train without dropout, as dropout increases a model's s robustness to ablating subnetworks. We train without weight decay, as we will apply Le regularization during mask training.

---

Test Target Subroutine and Test Other Subroutine. Finally, for each subnetwork, Sub,, we create Mc Sub and evaluate it on Test Target Subroutine and Test Other Subroutine"
Mablate,
6 Language Experiments
Tasks: We use a subset of the data introduced in Marvin & Linzen (019)) to construct odd-one-out tasks for language data. Analogous to the vision domain, odd-one-out tasks consist of four sentences, three of which follow a rule and one of which does not. We construct rules based on two forms of syntactic agreement: Subject- Verb Agreement and Reflexive Anaphora agreement 10 In both cases, the agreement takes the form of long-distance coordination of the syntactic number of two words in a sentence. First, consider the subject-verb agreement, the phenomenon that renders the house near the fields is on fire grammatical, and the house near the fields are on fire not grammatical.
Accordingly, define the following sentence types for Subject- Verb agreement: ((Singular/Phural) Subject, (Singular/Plural) Verb). Because both (Singular Subject, Singular Verb) and (Plural Subject, Plural Verb) result in a grammatical sentence, we partition the Subject-Vertt Agreement dataset into two subsets, one that targets singular sentences and one that targets plural sentences For the Singular Subject-Vert Verb Agreement dataset, base models are trained on compositional rule that defines (Singular Subject, Singular Verb) sentences to be rule-following, and (Plural Subject, Singular Verb) and (Singular Subjeet, Plural Verb) sentences be the odd-one-out, Thus, an odd-one-out example might look like: the picture by the ministers interest people. All other tasks are constructed analogously to those used the vision experiments (See Section The Reflexive Anaphora dataset is constructed simlarly (See Appendix F
The language experiments proceed analogously to the vision experiments. The only difference in the procedure that we take the representation of the [CLS] token to be the embedding of the sentence and omit the MLP. We study one architecture, BERT-Small (Bhargava et al., 2021 Ture et al. 2019). which is BERT architecture with 4 hidden layers (Devlin al. 20188).
Methods:
7 Results
Most base models perform near perfectly, with the exception of ViT, which failed to achieve >90% performance on any of the tasks with any configuration of hyperparameter [ Thus, exclude VIT from all subsequent analyses. See Appendix for these results. If the base models exhibit structural compositionality,
expect subnetworks to achieve greater accuracy on Test Target Subroutine than on Test Other Subroutine (difference in accuracies > 0). After ablating subnetworks, we expect the ablated model achieve greater accuracy Test Other than Test Target (difference in accuracies < 0). Across the board, we see the expected pattern. Subnetwork and ablated accuracy differences for Resnet50 and BERT are visualized Figure ( (Subnetwork in Blue, Ablated Models in Red). See Appendix A for Wide Resnet50 results, which largely reproduce the results using Resnet50.
For some architecture/task combinations, the pattern of ablated model results is statistically signifi- cantly in favor of struetural compositionality. See Figure/[CC D), where all base models seem to implement both subroutines in a modular fashion. We analyze the layerwise overlap between subnet- works found within one of these models in Appendix K This analysis shows that there is relatively high overlap between subnetworks for the same subroutine, and low overlap between subroutines. Other results are mixed, such as those found in Resnet50 models trained on Number-Contar Here.
'W used NVIDIA GeForce RTX 3090 GPUs for all experiments. Every experiment can be run single GPU, in approximately 1 GPU-hour. After performing a hyperparameter search. main results took approximately 300 GPU-hours.
Note that we are interested only in discovering some evidence of modularity within the model rather than looking for some more profound syntactic phenomenon.
See Appendix for more details
12eee Table 2 Appendix(A for each base model's performance the relevant compositional task.
AAll accuracy values are clamped to the range [0.25, 1.0] before differences are computed. 0.25 is chance accuracy. Constraining values to this range prevents false trends from arising in the difference data due to models performing below chance.
7

---

Resnet50 BERT Small Target Other)
Contact
Inside
Numbar-Contact
0.33
0.7
030
038
022
023
042
025
040
A-0
1odde
Contact
6.0
000
008
000
000
1,00
-3.2
-0.2
-3.00
Semt
5 5.Bnetwork Ablotion
Subnetwo &. Ablotion
Subnetwork Ablotio
5.bnetwork Abbation
Submeewark AMM
Subnebwork Ablocon
Anaphora
Agreement
LX4
AA
67%-
575-
0.50
659
055
1.00
0.2
0:25
0.2
1:25
Phritbat
0:30
-022
-1.23
Submetwork
Abration
Subretwcrk
Ablation
Submebwark
Ablatioo
Ablition
Figure 4: Results from Subnetwork and Ablation studies. For each compositional task, we learn binary masks that result in subnetworks for each subroutine. Resnet50 results in the top BERT- Small results the bottom row. Gray markers indicate that the corresponding base model did not achieve 90% accuracy performance on Test Target Subroutine and Test Other Subroutine. a model exhibits structural expect that subnetwork will achieve greater performance the subroutine that it was trained to implement, resulting in values >> O. (Red) After ablating the subnetwork, we evaluate the same datasets and plot the difference again. We expect that the ablated model will achieve lower performance on the subroutine that the (ablated) subnetwork was trained to implement and higher performance on the other subroutine dataset, resulting in values we find that our results are largely significantly different from O, despite the small number of samples. #s indicates significance at p .01, #** indicates significance p = .001 See Appendix A details of this statistical analysis.
the compositional task. (Blue) The difference between subnetwork
compositionality,
Across the board,
we see strong evidence structural compositionality in Figure 4 (E), but little evidence for it in Figure 4 (F). In this case, it appears that the network is implementing the (+/- Contact) subroutine in a small, modular subnetwork, whereas the (+/- Number) subroutine is implemented more diffusely. We perform control experiments using randomly initialized models in Appendix [ which show that the pattern of results in (A), (B) and (F) are not significantly different from a random model, while all other results are significantly different.
8 Effect of Pretraining on Structural Compositionality
We compare structural compositionality in models trained from scratch to those that were initialized with pretrained weights. For Resnet50, we pretrain a model on our data using SimCLR (See Appendix G for details).
For BERT-Small, we use the pretrained weights provided by Ture al. (2019). We rerun the same procedure described in Sections[]andd See Appendix[A]for each base model's performance. Figure contains the results the language experiments. Across all language tasks, the ablation results indicate that models initialized with pretrained weights more reliably produce modular subnetworks than randomly initialized models. Results on vision tasks are found in Appendix A and do not suggest any benefit of pretraining.
8

---

Subnetwork Performance: Randomly Initialized Models (Language)
Abletion 2
Subnetwork
Subnetwork
0.4
(PL
(9) pooo
(P) po
(0) Pros
(P) Sudyy
(P) suayy
(P) Sasyyy
(S) AsA..t
IS ASAAt
(S) StAtt:
(5) Pro.3
(5) Pro.
(5) Subj
Suuj 2
(5) Brsay
(9) vo.
(9) vpvv
(9 (9)
0.2
Performance
(9)
09)
(9)
(S)
Subnetwork Performance: Pretrained Models (Language)
-0.2
Ablation
-0.4
Ablation 3
Subnetwork
Subnetwork 3
(P) Ant.
69 Ant.
en Ant.
(P) Pro
(P) Pro
Pro
(9) mubii.2
(0) subj,
(9) suaj.
vo.
(P) vo.
(9 Ant.
(S) Pro.
Ra Subj.
Subji
(5) Suad.
vo.
(5)
Model
Figure 5: Performance differences between Test Target Subroutine and Test Other Subroutine for both models trained from scratch and pretrained models. Across the board, that pretraining produces more modular subnetworks (i.e., reveal a greater disparity in performance between datasets). Pretraining also appears make subnetwork-discover algorithm more robust random seeds.
Related Work
This work casts new lens on the study of compositionality in neural networks. Most prior work has focused on compositional generalization of standard neural models (Yu & Ettinger 2020 Kim
& Linzen 2020) Kim et al., 2022 Dankers et al.) 2022). though some has attempted to induce an inductive bias toward compositional generalization from data (Lake) 2019 Qiu al. 2021
Zhu et al.] (021). Recent efforts have attempted to attribute causality to specific components of neural networks' internal representations (Ravfogel et al. 2020 Bau al. 2019 Wu et al. 2022 Tucker al.) 2221 [overing & Pavlick] 2022 Elazar al. 202 |
Cao et al. 2021) In contrast to these earlier studies, our method does not require any assumptions about where in the network the subroutine is implemented and does not rely auxiliary classifiers, which
confound the causal interpretation. Finally, Dziri et al. 2023) performs extensive behavioral studics characterizing the ability of autoregressive language models to solve compositional tasks, and finds them lacking. In contrast, our work studies the structure of internal representations and sets aside problems that might be specific to autoregressive training objectives.
More directly related the present study the burgeoning field mechanistic interpretability, which aims to reverse engineer neural networks in order to better understand how they function (Olah] 2022 Cammarata et al. 2020; Black et al.) 2022 Henighan et al. 2023 Ganguli et al. 2021 Merrill et al. 2023). Notably, Chughtai et al. (2023) recovers universal mechanisms for performing group theooetic compositions. Though group-theorete composition different from the compositionality discussed in the present article, this work sheds light generic strategies that models may use to solve tasks that require symbolically combining multiple input features.
Some recent work has attempted to characterize modularity within particular neural networks (Hod) al., 2022). [Sordás al.) (202T) also analyzes modularity within neural networks using learned binary masks. Their study finds evidence of modular subnetworks within multitask network: Within a network trained to perform both addition and multiplication, different subnetworks arise for each operation. Csordás al. (2021) also investigates whether the subnetworks are reused in variety of contexts, and find that they are not. In particular, they demonstrate that subnetworks that solve particular partitions of compositional datasets (SCAN Lake & Baroni 2018) and the Mathematics

---

Dataset (Saxton et al. 2018)), oftentimes do not generalize to other partitions. From this, they conclude that neural networks do not flexibly combine subroutines in a manner that would enable full compositional generalization. However, their work did not attempt to uncover subnetworks that implement specific compositional subroutines within these compositional tasks. For example, they did not attempt to find subnetwork that implements general "repeat" operation for SCAN, transforming "jump twice" into "JUMP JUMP". Our work finds such compositional subroutines in language and vision tasks, and localizes them into modular subnetworks. This finding extends Csordás et al. (202T)ss result on a simple multitask setting to more complex compositional vision and language settings, and probes for subroutines that represent intermediate subroutines in compositional task (i.e. "inside" " a subroutine when computing Iuside-Contact""
10
Discussion
Across a variety of architectures, tasks, and training regimens, we demonstrated that models often exhibit structural compositionality. Without any explicit encouragement to do so, neural networks appear decompose tasks into subroutines and implement solutions to (at least some of) these subroutines in modular subnetworks. Furthermore, we demonstrate that self-supervisse pretraining can lead to more consistent structural compositionality, at least in the domain of language. These results bear on the longstanding debate over the need for explicit symbolic mechanisms in Al systems. Much work is focusing on integrating symbolic and neural systems (Ellis et al. 2023 Nye et al.) 2020). However, our results suggest that some simple pseudo-symbolic computations might be learned directly from data using standard gradient-bast based optimization techniques.
We view our approach as tool for understanding when and how compositionality arises in neural networks, and plan to further investigate the conditions that encourage structural compositionality One promising direction would be to investigate the relationship between structural compositionality and recent theoretical work on compositionality and sparse neural networks (Mhaskar Poggio 2016 Poggio 2022). Specifically, this theoretical work suggests that neural networks optimized to solve compositional tasks naturally implement sparse solutions. This may serve as a starting point for developing formal theory of structural compositionality in neural networks. Another direction might be to investigate structural compositionality of networks trained using iterated learning procedures (Ren al. 2019; Vani et al. 2020). Iterated learning simulates the cultural evolution of language by jointly trainig two communicating agents (Kirby et al.) 2008). Prior work has demonstrated that iterated learning paradigms give rise simple compositional languages. Quantifying the relationship between structural compositionality within the agents and the compositionality of the language that they produce would be an exciting avenue for understanding the relationship between representation and behavior.
One limit of our technical approach is that one must specify which subroutines to look for in advance. Future work might address this by discovering functional subnetworks using unsupervised methods. Additionally, our approach requires us use causal ablations and control models to properly interpret our results. Future work might try to uncover subnetworks that are necessarily causally implicated in model behavior. Finally, future work must clarify the relationship between structural compositionality and compositional generalization.
Acknowledgments and Disclosure of Funding
The authors thank the members of the Language Understanding and Representation Lab and Serre Lab for their valuable feedback on this project and Rachel Goepner for proofreading the manuscript. This project was supported by ONR grant #N00014 The computing hardware was supported in part by NIH Office of the Director grant #S #S100D025181 via the Center for Computation and Visualization (CCV) at Brown University.
References
Andreas, J., Rohrbach, M., Darrell, T., and Klein, Neural module networks. Proceedings of the IEEE conference computer vision and pattern recognition, pp. 39-48, 2016.
10

---

Bau, A., Belinkov, Y., Sajjad, H., Durrani, N., Dalvi, F., and Glass, J. Identifying and control- ling important neurons neural machine translation. In International Conference on Learning Representations, 2019, URL https:://pppereeeeeeee wwtp://ooorrndddd----eeeeeee
Bhargava, P., Drozd, A., and Rogers, A. Generalization in nli: Ways (not) to go beyond simple heuristics. In Proceedings of the Second Workshop on Insights from Negative Results in NLP, pp. 125-135, 2021.
Black, S., Sharkey, L.,, Grinsztajn, L., Winsor, E., Braun, D., Merizian, J., Parker, K., Guevara, C. R., Millidge, B., Alfour, G., al. Interpreting neural networks through the polytope lens. arXiv preprint arXiv:2211.1233 2022.
Cammarata, N., Carter, S., Goh, G., Olah, C., Petrov, M., Schubert, L.,, Voss, C., Egan, B., and Lim, S. K. Thread: Circuits. Distill, 5(3)x224, 2020.
Cao. S., Sanh, V., and Rush, A. M. Low-complexity probing via finding subnetworks. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 960-966, 2021.
Chen, T., Korblith, S., Norouzi, M., and Hinton, G. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pp. 1597-1607. PMLR, 2020.
Chughtai, B., Chan, L., and Nanda, N. A toy model of universality: Reverse engineering how networks learn group operations. arXiv preprint arXiv:2302.03025, 2023.
Csordás, R., van Steenkiste, S., and Schmidhuber, J. Are neural nets modular? inspecting func- tional modularity through differentiable weight masks. In International Conference on Learning Representations, 2021.
Dankers, V., Bruni, E., and Hupkes, D. The paradox of the compositionality of natural language: neural machine translation case study. In Proceedings of the 60th Anmual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp.
2022.
De Cao, N., Schlichtkrull, M. S., Aziz, W., and Titov, I. How do decisions emerge across layers in neural models? interpretation with differentiable masking. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 3243-3255, 2020.
De Cao, N., Schmid, L., Hupkes, D., and Titov, Sparse interventions in language models with differentiable masking. In Proceedings of the Fifth BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP, pp. 16-27, 2022.
Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 2018.
Dosovitskiy, A., Beyer, I.., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. An image worth 16x 16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2020.
Dziri, N., Lu, X., Sclar, M., Li, X. L., Jian, L., Lin, B. Y., West, P., Bhagavatula, C., Bras, R. L., Faith and fate: Limits of transformers on compositionality. arXiv preprint
Hwang, D., et 1785 2023.
Elazar, Y., Ravfogel, S., Jacovi, A., and Goldberg, Y. Amnesic probing: Behavioral explanation with amnesic counterfactuals. Transactions of the Association for Computational Linguistics, 9: 160-175, 2021.
Ellis, K., Wong. L., Nye, M., Sable-Meyer, M., Cary, L., Anaya Pozo, L., Hewitt, L., Solar-Lezama, A., and Tenenbaum, J. B. Dreamcoder: growing generalizable, interpretable knowledge with wake-sleep bayesian program learning. Philosophical Transactions of the Royal Society A, 381 (2251):20220050, 2023.
Ettinger, A., Elgohary, A., Phillips, C., and Resnik, P. Assessing composition in sentence vector representations. In Proceedings of the 27th International Conference on Computational Linguistics, pp. 1790-1801, 2018.
11

---

Fodor, J. A. and Lepore, E. The compositionality papers. Oxford University Press, 2002.
Ganguli, D., Hatfield-Dodds, Z., Hernandez, D., Jones, A., Kernion, J., Lovitt, L., Ndousse, K., Amodei, D., Brown, T., Clark, J., Kaplan, J., McCandlish, S., and Olan, C. A mathematical framework for transformer circuits. Transformer Circuits Thread, 2021.
Guo, D., Rush, A. M., and Kim, Y. Parameter-efficient transfer learning with diff pruning. In Proceedings of the 59th Anmual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 4884 4896, 2021.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Henighan, T., Carter, S., Humne, T., Elhage, N., Lasenby, R., Fort, S., Schiefer, N., and Olah, C. Superposition, memorization, and double descent. Trunsformer Circuits Thread, 2023.
Hod, S., Filan, D., Casper, S., Critch, A., and Russell, S. Quantifying local specialization in deep neural networks. arXiv e-prints, pp. arXiv-2110, 2022.
Hupkes, D., Dankers, V., Mul, M., and Bruni, Compositionality decomposed: How do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795, 2020.
Kim, N. and Linzen, T. Cogs: A compositional generalization challenge based semantic interpre- tation. In Empirical Methods in Natural Language Processing, 2020.
Kim, N., Linzen, T., and Smolensky, P. Uncontrolled lexical exposure leads to overestimation of compositional generalization in pretrained models. arXiv preprint arXiv:2212. 2022.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint 141.v:1412.6998, 2014.
Kirby, S., Cornish, H., and Smith. K. Cumulative cultural evolution in the laboratory: An experimental approach the origins structure in human language. Proceedings of the National Academy of Sciences, 105(31): )): 106110011100 10686, 2008.
Koh, P. W., Nguyen, T., Tang. S., Mussmann, S., Pierson, E., Kim, B., and Liang, P. Concept bottleneck models. In International Conference on Machine Learning, pp. 3338-5348. PMLR, 2020.
Lake, B. and Baroni, M. Generalization without systematicity: On the compositional skills of sequence-to-sequenee recurrent networks. In International conference machine learning, pp- 2873-2882. PMLR, 2018.
Lake, B. M. Compositional generalization through meta sequence-to-sequence learning. Advances in neural information processing systems, 32, 2019.
Lake, B. M., Ullman, T. D., Tenenbaum, J. B., and Gershman, S. Building machines that learn and think like people. Behavioral and brain sciences, 40, 2017.
Lippe. P.
Tutorial 17:
Self-supervised contrastive learning with simelr.
https
//ithub. com httppp//w..a.....ttooo/////////p tutoriall7/SimCin ipynb, 2022.
Louizos, C., Welling, M., and Kingma, D. Learning sparse neural networks through I_0 regulariza- tion. In International Conference on Learning Representations, 2018.
Lovering, C. and Pavlick, E. Unit testing for concepts in neural networks. Transactions of the Association for Computational Linguistics, 10:1 193-1208, 2022.
Mandelbaum, E., Dunham, Y., Feiman, R., Firestone, C., Green, E., Harris, D., Kibbe, M. M., Kurdi, B., Mylopoulos, M., Shepherd, J., al. Problems and mysteries of the many languages of thought. Cognitive Science, 46(12): 2022.
12

---

Marcus, G. F. The algebraic mind: Integrating connectionism and cognitive science. MIT press, 2003.
Marvin, R. and Linzen, T. Targeted syntactie evaluation of language models. Proceedings of the Society for Computation in Linguistics (SCiL), pp. 573-374, 2019.
Merrill, W. Tsilivis, N., and Shukla, A. A tale of two circuits: Grokking as competition of sparse and dense subnetworks. In ICLR 2023 Workshop on Mathematical and Empirical Understanding of Foundation Models, 2023.
Mhaskar, H. N. and Poggio, Deep vs. shallow networks: An approximation theory perspective. Analysis and Applications, 12906))829-848, 2016.
Nye, M., Solar-Lezama, A., Tenenbaum, J., and Lake, B. M. Learning compositional rules via neural program synthesis. Advances in Neural Information Processing Systems, 33: 13:3222-10842, 2020.
Olah, C. Mechamistic interpretabilityy. variables, and the importance of interpretable bases. Trans- former Circuits Thread, 2022.
Piantadosi, S. T., Tenenbaum, B., and Goodman, N. D. The logical primitives thought: Empirical foundations for compositional cognitive models. Psychological review, 123(4):392, 2016.
Poggio, T. How deep sparse networks avoid the curse of dimensionality: Efficiently computable functions are compositionally sparse. CBMM Memo, 10:2022, 2022.
Qiu, L., Shaw, P., Pasupat, P., Nowak, P. K., Linzen, T., Sha, F., and Toutanova, K. Improving composi- tional generalization with latent structure and data augmentation. arXiv preprint (r 2021.
muntt,-Dun,, J., Porot, N., and Mandelbaum, E. The best game in town: The re-emergence of the language of thought hypothesis across the cognitive sciences. Behavioral and Brain Sciences, pp. 1-55, 2022.
Ramanujan, V., Wortsman, M.. Kembhavi, A., Farhadi, A., and Rastegari, M. What's hidden in randomly weighted neural network? In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11893-1199100 11902, 2020.
Ravfogel, S., Elazar, Y., Gonen, H., Twiton, M., and Goldberg, Y. Null it out: Guarding protected attributes by iterative nullspace projection. In Proceedings the 58th Annual Meeting of the Association for Computational Linguistics, pp. 7237-7256, 2020.
Ren, Y., Guo, S., Labeau, M., Cohen, S. B., and Kirby, S. Compositional languages emerge in a neural iterated learning model. In International Conference on Learning Representations, 2019.
Savarese, P., Silva, H., and Maire, M. Winning the lottery with continuous sparsification. Advances in Neural Information Processing Systems, 33:1 1380-11390, 2020.
Saxton, D.,, Grefenstette, E., Hill, F., and Kohli, P. Analysing mathematical reasoning abilities of neural models. In International Conference on Learning Representations, 2018.
Smolensky, P., McCoy, R., Fernandez, R., Goldrick, M., and Gao, J. Neurocompositional computing: From the central paradox of cognition to new generation of ai systems. Magazine, 43))): 2022.
Tucker, M., Qian, P., and Levy, R. What if this modified that? syntactic interventions with counter- factual embeddings. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pp. 862 875, 2021.
Ture. I., Chang. M., Lee, K., and Toutanova, K. Well-read students learn better: The impact of student initialization on knowledge distillation. CoRR, //arxiv.. , org/ abs/ 190// 08962
2019. URL http:
Vani, A., Schwarzer, M., Lu, Y., Dhekane, E.,, and Courville, A. Iterated learning for emergent systematicity in vqa. In International Conference Learning Representations, 2020.
13

---

Wortsman, M., Ramanujan, V., Liu, R., Kembhavi, A., Rastegari, M., Yosinski, J., and Farhadi, A. Supermasks in superposition. Advances Neural Information Processing Systems, 33:15173- 15184, 2020.
Wu, Z., Geiger, A., Rozner, J., Kreiss, E., Lu, H., Ieard, T., Potts, C., and Goodman, N. Causal distillation for language models. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 4288 4295, 2022.
Yu, L. and Ettineer, A. Assessing phrasal representation and composition in transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 4896-4907, 2020.
Zagoruyko, S. and Komodakis, N. Wide residual networks. In British Machine Vision Conference 2016. British Machine Vision Association, 2016.
Zerroug, A., Vaishnav, M., Colin, J., Musslick, S., and Serre, benchmark for compositional visual reasoning. In siitt Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
Zhang, D., Ahuja, K., Xu, Y. Wang, Y., and Courville, A. Can subnetwork structure be the key to out-of-distributtinn generalization? In International Conference Machine Learning, pp- 12356-1 12367. PMLR, 2021.
Zhou, H., Lan, J., Liu, R., and Yosinski, J. Deconstructing lottery tickets: Zeros, signs, and the supermask. Advances in neural information processing systems, 32, 2019.
Zhu, W. Shaw, P., Linzen, T., and Sha, F. Learning generalize compositionally by transferring across semantic parsing tasks. arXiv preprint arXiv:2111.05015 2021.
14

---

CОMP. TASK
MODEL
SR
INTERCEPT Z
LINEAR HYPOTHESIS x²
IN. CONT.
RN50
INSIDE
50. +
1,42
IN. CONT.
RN50
CONTACT
3.00**
0.94
IN. CONT.
WRNSO
INSIDE
6,66
0.87
IN. CONT.
WRNS0
CONTACT
7
4,49*
IN. NUM.
RN50
INSIDE
11.1391
29. 29.20
IN. NUM.
RN50
NUMBER
18.35
21.73***
IN. NUM.
WRN50
INSIDE
14.86
2.95.
IN. NUM.
WRN50
NUMBER
5.21
2.50
CONT. NUM.
RN50
CONTACT
6,45
40.26***
CONT. NUM.
RN50
NUMBER
7.12**4
0.42
CONT. NUM.
WRN50
CONTACT
6.19
296.96***
CONT. NUM.
WRNS0
NUMBER
9.388***
1.32
SV AGR
BERT
SUBL
4.53#**
14.72***
SV AGR
BERT
VERB
3.73**4
1.70
ANAPHORA
BERT
PRONOUN
6.06***
5.60*
ANAPHORA
BERT
ANTECEDENT
2.60
17.83
Table 1: Statistics from one factor GLM with robust clustered standard errors. indicates significance
at p = .1, * indicates significance p .05, ** indicates significance p = ,01, *** indicates significance at = .001
A Full Results
In this section, we provide the following results:
1. Base Model Performance on Compositional Tasks: Table _
2. Pretrained + Finetuned Model Performance on Compositional Tasks: Table
3. Wide Resnet50 Subnetwork Results: Figure 6
4. Vision Pretraining vs. Random Initialization Heatmap: Figure
5. Absolute Accuracy for every subnetwork and ablated model on each task, for each model: Figures 12
See Table 2 for the performance of all base models on each compositional task. See Table 3 for the performance of pretrained base models on each compositional task. See Figure for subnetwork and ablation results on Wide Resnet50. See Figure 7 for Vision Model pretraining results.
A.1 Statistical Analysis of Main Results
In order to assess the significance of our main results, we fit a generalized linear model (GLM) with robust clustered standard errors for each combination of model architecture, compositional task, and subroutine. This GLM includes a dummy variable indicating whether the results are from subnetwork an ablated model, and clusters observations by base model. For language experiments, we collapse across singular and plural instances of the same subroutine. The intercept term in this model assesses whether the performance of the discovered subnetworks are significantly different from O. From this model, we can also perform linear hypothesis test to assess whether ablated model performance significantly different from Table provides the relevant statistics. Across the board, we see that there is always significant difference between subnetwork performance and 0, and often significant difference between ablated model performance and O, even with a small sample size.
15

---

VISION
CONT.- INSIDE
CONT.-
INSIDE-
NUMBER
NUMBER
RN50-1
100%
99.4%
99.8%
N
100%
99.4%
99.8%
RN5003
75.9%
99.7%
99.9%
WRN50-1
99.9%
99.6%
99.7%
WRN50-2
99.8%
99.8%
99.6%
WRN50-3
99.9%
99.4%
99.8%
LANGUAGE
SV
SV
ANAPH. SING.
ANAPH.
SING.
PLUR.
PLUR.
BERT-SM-1
99.7%
100%
100%
100%
BERT-SM-2
100%
100%
100%
100%
BERT-SM-3
100%
100%
100%
100%
Table 2: Test classification accuracy for each base model for each task. Every entry corresponds to unique model.
VISION
CONT.- INSIDE
CONT.- NUMBER
INSIDE-
NUMBER
RN50-SC-1
100%
99.7%
100%
RN50-SC-2
100%
99.6%
99.8%
RN50-SC-3
100%
99.5%
99.9%
LANGUAGE
SV
SV
ANAPH. SING.
ANAPH.
SING.
PLUR.
PLUR.
BERT-LM-I
100%
100%
100%
100%
BERT-LM-2
100%
100%
65.5%
100%
BERT-LM-3
100%
100%
63.5%
100%
Table 3: Test classification accuracy for each pretrained base model for each task. Every entry corresponds to a unique model.
Wide Resnet50 (Test Target Test Other)
Inside Contact
Inside Number
Number Contact
150
1.00
1.0
103
1.0
0.13
5.0
0.0%
026
Conmact
+1.00
-1.0
-1.00
-1.00
Allation
Figure 6: Wide Resnet50 Subnetwork and Ablation Results. Broadly, they mimic those found in
Figure 4 indicates significance at p= .1, indicates significance at p .05, ** indicates significance
p 01, sas indicates significance p .001.
16

---

Subneawark Performance: Randomly Initielized Models (Vision)
0.2
Porformance
oid conmoct
no voddee
Coonuc
Connter
00 Nunber
(
Model
-0.2
Subbeeworkk Performance: Pretrained Models (Vision)
0.4
ei commort
no vosdle
URD Coonuct
Conkee
OeC Conneer
Mondber
Monderr
no
Model
Figure 7: Vision Model Pretraining vs. Random Initialization. differentiating the two conditions.
We observe no obvious trend
Resnet50 Subnctwoo Contact
Subnetworiz: Number
Subnatwerks: Contact
19200
CONTECT
Tirget
Other
Other
Other
Diner
Other
Other
Be Ablated No EuriaatCrraac
Bevee50 Atritted Natmoris Iraade-Nunnter
Reeewt50 Attated Net Nambre-Conaat
1.-
12-
endie
Cortact
Namber
Target
Tirget
Target
Target
Target
Other
Trrget
Figure 8: Resnet50 absolute performance across all conditions,
B Continuous Sparsification: Extended Discussion
Continuous sparsification attempts to optimize binary mask that minmizes the following loss function:
min m0.))
Lsn, (Mc @ m;)) Al|m|]h
(1)
17

---

WiscResnat50 Subnetwerkz: Indido Contact
WideResnat50 Subrebworks: inside Numbor
Widencsna550 Subnetwerks: Number Contact
10
19500
Contact
Mambee
6.2
13/ger
Iarget
100get
seget
brgge
WAdeReeseet0 Aslatod Networkss: Contact
Wocckssne550 Networks:
MideRcsnetSo Networks: Contact
115.0c
Mamber
13nger
other
langen
uther
tbnget
other
orggt
ofter
weget
other
wriget
Lther
Figure 9: Wide Resnet50 absolute performance across all conditions
Sulamimor''s InviattCrrtacl
Salmetomkk: Costhe-oontatt
M
3
022
099
Tirget
Other
30
Tirget
Other
Other
Diser
Other
Trrget
Cther
Resmut50 + SinCL Ablated Nucamokks Contac-Crntac
Resnst50 Sin Aslatied Networiss: Inaide-Number
Raunet50
SmILR Ablacue Networks: Inside-Contact
30
Contac
C44
Tirget
Tarret
Target
Ttogge
Dttter
Target
Other
Terget
Figure 10: Resnet50 SimCLR absolute performance across all conditions.
The first term describes the standard loss function given by an odd-one-out task where the rule is defined by SR; The second term corresponds to the Lo penalty, which encourages entries in the binary mask to be 0. However, optimizing such a binary mask is intractable, given the combinatorial nature of a discrete binary mask over large parameter space. Instead, continuous sparsífication reparameterizes the loss function by introducing another variable, E Rdd
min LSR (Mo w Nowwwwo 0 s:)) + A1 s:) #cERd
In Equation 2 is the sigmoid function, applied elementwise, and 3 is temperature parameter. During training 3 is increased after each epoch according to an exponential schedule to a large value 8maz. Note that, as B + a(3 s4) + H (s:), where H (s:) is the heaviside function.
18

---

BERT Small Subnetworks: Anaphora
BERT Small Subnetworks: SV Agreement
ORAADE
1G
QPAADE
GRAADR
1.3
Anaphores Pranour
08-
Anaphora: Antecedent
0.8
5V Agreement: Subject
0.5
SV Agreeneent:
0.0
0.6
0.6
0.5
0.-
0.4
0.4
0.4
*ga
0.-
0.2
0.-
0.2
0.0
0.9
Target
Other
Target
Other
Target
Other
Target
Other
BERT Small Ablated Networks: Anaphora
BERT Small Ablated Networks: SV Agreement
Anaghara: Pronoun
0.8
Anapho a: Antecedent
0.8
SV Agreament Subjoct
SV Agreemennt:: Verbb
0.8
0.4
0.6
0.4
0.4
0.4
0.4
02
02
0.
9.2
0.0
0.0
0.0
Target
Other
Target
Other
Target
Other
Target
Other
Figure BERT-Small absolute performance across all conditions
H(s) = { 0,8 < 1,8 }
(3)
Thus, during training, interpolate between soft mask (a) and discrete mask (H). During inference, we simply substitute (8 : 5;)) for (s;). Notably, we apply continuous sparsification to frozen model in attempt to reveal the internal structure of this model, whereas the original work introduced continuous sparsification in the context of model pruning, and jointly trained w and
Following Savarese et al. 2000)), we fix Bmar 200, X = 10-8 and train for 90 epochs. train the mask parameters using the Adam optimizer with a batch size of 64 and search over learning rates.
C Mask Hyperparameter Search Details
We search over learning rates (.01, .0001001 ). mask parameter initializations (0.1, 0.05, 0.0, -0.05), and mask configurations. For Resnet models, search over mask configurations by starting masking at different stages. We try either (I) masking the whole network, (2) beginning masking at the third (of four) stages), and (3) beginning masking at the fourth stage. For transformer models, search over mask configurations based on layers. We try either (1) masking the whole networks, (2) beginning masking the third (of four) layers, (3) beginning masking at the fourth layer.
perform this search independently for each trained model perparameter configuration is determined based the following criteria: The subnetwork must achieve at least 90% accuracy on the task it was trained on. This to ensure that mask optimization succeeded. Then, it was scored on its degree of structural compositionality using the validation sets
each subroutine. The best hy-
19

---

BERT Small LM Subnetworks: Anaphora
BERT Small + LM Subnetworks: SV Agreement
ORAADE
1G
GRAADE
GRAADR
1.3
GRAADE
08-
Anaphora. Antecedent
0.8
5V Agraement: Subject
0.5
Anaphores Pranour
SV Agreeneent: Ver
0.6
0.6
0.6
0.5
0.-
0.4
0.4
0.4
0.-
0.2
0.-
0.2
0.0
0.0
Target
Other
Target
Other
Target
Other
Target
Other
BERT Small + LM Ablated Natworks: Anaphora
BERT Small + LM Ablated Networks: SV Agreement
Anaghara: Pronoun
0.-
Anapho a: Antecedent
0.8
SV Agreamentt Subject
SV Agreementt: Verb
0.8
n.-
0.4
0.6
0.4
0.4
0.4
0.4
0.2
0.2
02
0.2
0.0
0.0
0.0
Target
Other
Target
Other
Target
Other
Target
Other
Figure 12: BERT-Small + LM absolute performance across all conditions.
of Test Target Subroutine and Test Other Subroutine If subnetwork is trained to implement SR1- then its compostionality score is calculated using Mablate Mc Suby. The score is simply the difference in accuracy that Matlate, achieves on Test Other Subroutine (which the ablated model should perform well on) and Test Target Subroutine (which the ablated model should fail on). All accuracies are clamped in the range [.25, 1], as .25 is chance accuracy. The hyperparameters that maximize this score are returned.
Note that this process is fairly computationally expensive, as it requires training many separate masks. We used NVIDIA GeForce RTX 3090 GPUs for all experiments. Every experiment can be run single GPU, in approximately I GPU-hour. The entire hyperparameter search takes approximately 2448 GPU-hours. This number was computed follows: GPU-hour model seeds * 2 learning rates 4 initializations subroutines Wide Resnet50 subroutines + BERT subroutines + pretrained BERT subroutines). Each mask has parameter count comparable to its base model. Future work could improve upon the methodology presented here by reducing the number of hyperparameters that one must search over.
mask configurations (6 Resnet50 subroutines + 6 pretrained Resnet50
D ViT Hyperparameter Search Results
See Table for the results of our hyperparameter search on VIT models. We tried several batch sizes and learning rates both a 6 and 12 layer ViT, all with 2 layer MLP head. The MLP had hidden layer of dimensionality 2048, and an output dimensionality of 128, similar to the Resnet50 and Wide Resnet50. Note that all models fall short of solving any of the tasks.
20

---

LAYERS
BATCH SIZE
LEARNING RATE
CONT.-NUMBER
INSIDE-NUMPI
32
0.01
31%
27%
28%
64
0.01
28%
29%
27%
32
0.001
29%
27%
28%
6
64
0.001
32%
%
26%
6
32
0.0001
25%
32%
30%
64
0.0001
31%
49%
32%
32
0.00001
42%
85%
47%
6
64
0.00001
46%
83%
54%
12
32
0.01
36%
25 %
28%
12
64
0.01
27%
26 %
25%
12
32
0.001
39%
31 %
27%
12
64
0.001
37%
25 %
22%
12
32
0.0001
41%
36%
33%
12
64
0.0001
31%
28%
31%
12
32
0,00001
40%
86 %
49%
12
64
0.00001
42%
84% %
51% 1
Table Results of ViT hyperparameter search. All accuracies rounded the nearest % and computed on the validation set for the relevant dataset.
E
Vision Stimuli
In this section, we provide examples from all vision datasets that we use this work. First, we describe the +/- Number subroutine. This subroutine operates as follows: for each training/test example, let N be an integer. All image types that exhibit (+ Number) will contain shapes, whereas image types that exhibit Number) will contain M shapes, M * N. For a description of the other subroutines, refer back to Section
F Language Data Details
As noted in the main text, our language data is generated using the templates provided by Marvin & Linzen (2019). For subject-verb agreement datasets, we omit templates that position the noun of interest inside either sentential complement or object relative clause. Thus, all of our nouns of interest are the subject the full sentence. This done in order to render the (Singular/Plural Subject) subroutine unambiguous across different sentence templates. We do the same for the Reflexive Anaphora datasets, removing the template that positions the antecedent inside a sentential complement.
These exclusions mean that the nouns of interest are always the second word of the sentence. This makes the (Singular/Plural Subject) subroutine amenable to simple heuristic: check the syntactic number of the second word the sentence, rather than first needing to identify the subject of sentence. However, we are unconcerned about this heuristic: the present work makes no claims about how a neural network implements any particular subroutine, instead caring about how several subroutines are organized in the network's 's weights (i.e. are they represented compositionally. or in an entangled fashion?).
Specifically, the subroutines we examine are those that compute the syntactic number of specific words in a sentence (either subject and verb, or antecedent and pronoun). Our goal is find subnetworks that implement these subroutines. Consider the case of subject verb agreement. If we were to partition our data precisely analogously to the vision datasets, we would arrive compositional dataset where rule-following data points exhibit, say, (Singular Subject, Singular Verb), and rule breaking examples might exhibit any of (Plural Subject, Singular Verb), (Singular Subject, Plural Verb), (Plural Subject, Plural Verb). However, one might expect that pretrained network would implement syntactic number subroutines in service another salient computation: discerning whether sentence is grammatical or not. In this case, a pretrained model would need to
21

---

D
Figure 13: Examples from tasks defined over the Uside-Contad compositional rule. From top to bottom, we see one example from each of the following tasks: (1) The task used to train base models (2) The task used to train Contact subnetwork (3) The task used to train +/- Inside subnetwork (4) The evaluation task used to probe for +/- Contact (5) The evaluation task used to probe for +/- Inside.
unlearn this grammaticality computation, forcing two grammatical sentences apart in its embedding space. In order to avoid this potential complication, split up datasets into singular and plural partitions, such that only rule-following examples are grammatical (and aule-breaking examples ungrammatical) in each compositional dataset and subroutine test
Note that these datasets are smaller than those used for the vision experiments. Using the Marvin & Linzen (2019) templates and their provided vocabulary, and discarding the templates noted above, we arrive at the following dataset statistics (which are identical for the singular and plural instances of each dataset). For each, provide on singular example and one plural example. The odd one out is always the fourth sentence.
Subject-Vers Verb Agreement: Compositional Dataset: 9500 (Train), 500 (Validation), 1000 (Test)
Singular
the farmer near the parent old
2. the surgeon that the architects hate laughs
3. the novel that the dancer likes is new the senator to the side of the parents are young
Plural
1. the farmers the taxi drivers love are short
2. the songs the dancers admire unpopular
the surgeons that admire the executives are young
4. the officers that love the assistant is short
22

---

Figure 14: Examples from tasks defined over the Inside-Number compositional rule. From top to bottom, we see one example from each of the following tasks: (1) The task used to train base models (2) The task used to train a +/- Inside subnetwork (3) The task used to train +/- Number subnetwork (4) The evaluation task used probe for +/- Inside (5) The evaluation task used to probe for +/- Number.
Subject- Verb Agreement: (Singular/Plural Subject) Dataset: 9500 (Train), 500 (Valida- tion), 1000 (Test)
Singular
1. the farmer that the taxi driver hates smile
2. the consultant the guards hate is young
3. the poem that the assistant likes brings joy to people
4. the customers that the chefs like is tall
Plural
1. the novels the guard hates are good
2. the teachers across from the parent is young
3. the shows that the taxi driver likes are unpopular
the manager across from the parent smile
Subject- Verb Agreement: (Singular/Plural Verb) Dataset: 9500 (Train), 500 (Validation), 1000 (Test)
Singular
1. the game the executives admire is unpopular
2. the surgeon to the side of the taxi drivers smiles
3. the consultants the dancer likes swims
the painting that the chefs love are unpopular
Plural
1. the customer the assistant loves swim
23

---

4
V
TV T
A44
AA4
Figure 15: Examples from tasks defined over the Number-Contact compositional rule. From top to bottom, we see one example from each of the following tasks: (1) The task used to train base models (2) The task used train a +/- Contact subnetwork (3) The task used train a +/- Number subnetwork (4) The evaluation task used to probe for +/- Contact (5) The evaluation task used to probe for +/- Number.
2. the surgeons that the executive likes are short
3. the authors that love the chef swim
the officers that like the assistant swims
Subject- Verb Agreement: Test (Singular/Plural Subject) Dataset: 300 (Validation), 300 (Test)
Singular
1. the teacher to the side of the taxi driver swims
2. the farmer that the chef likes is young
3. the novel the ministers admire is bad
4. the customers in front of the dancers is old
Plural
1. the pictures by the skater interest people
2. the movies the skater admires are bad
3. the pilots in front of the taxi driver are tall the consultant that the dancer likes old
Subject-Vent Verb Agreement: Test (Singular/Plural Verb) Dataset: 300 (Validation). 300 (Test)
Singular
1. the senator the taxi drivers admire is young
2. the pilot to the side of the dancer smiles
3. the farmer the assistant admires is young

---

4. the pilot that loves the minister are tall
Plural
1. the poems that the chefs hate are bad
2. the surgeons in front of the dancer laugh
the surgeons
the taxi drivers smile the farmers behind the architects short
Reflexive Anaphora:
Compositional Dataset: 2500 (Train), 200 (Validation), 200 (Test)
Singular
1. the consultant that the chef loves disguised himself
the manager that the architects hate congratulated herself
the pilot that the architects admire hurt herself
4. the surgeon that the executives like congratulated themselves
Plural
1. the consultants that the guards love injured themselves
2. the senators that the minister admires embarrassed themselves
the officers that the assistant likes embarrassed themselves
the teacher that the dancer loves embarrassed themselves
Reflexive Anaphora: (Singular/Plural Antecedent) Dataset: 2500 (Train), 200 (Valida- tion), 200 (Test) Singular
1. the officer that the taxi driver likes doubted herself
2. the author that the architect loves hated himself
3. the manager that the executives love disguised herself the customers that the parent likes disguised himself
Plural
1. the authors that the skater hates doubted himself the surgeons that the parents admire hurt themselves
the officers that the taxi driver hates injured himself
the pilot that the assistant loves hurt themselves
Reflexive Anaphora: (Singular/Plural Pronoun) Dataset: 2500 (Train), 200 (Validation), 200 (Test)
Singular
the customer that the ministers hate congratulated herself
the surgeons that the dancers like embarrassed himself
the authors that the taxi driver hates embarrassed himself
4. the author that the architect admires doubted themselves
Plural
officer that the skaters admire embarrassed themselves the senator that the guard likes embarrassed themselves
3. the customer that the ministers love doubted themselves
4. the managers that the guard admires injured herself
Reflexive Anaphora: Test (Singular/Plural Antecedent) Dataset: 200 (Validation). 200 (Test)
Singular
1. customer that skater admires hurt herself
the consultant that the executive loves disguised herself
3. the manager that the skaters like embarrassed herself
4. the senators that the guard admires injured himself
25

---

Plural
1. the senators that the architects like embarrassed themselves
the authors that the executives admire disguised themselves
3. the surgeons that the taxi driver admires doubted themselves
4. the officer that the parents like congratulated themselves
Reflexive Anaphora:
Test (Singular/Plural Pronoun) Dataset: 200 (Validation), 200
(Test)
Singular
1. the pilot that the chefs hate hurt himself
2. the teacher that the taxi drivers love hated herself
3. the senator that the assistant loves embarrassed herself the pilot that the skaters admire embarrassed themselves
Plural
1. the authors that the parents admire congratulated themselves
2. the pilots that the chef hates hurt themselves
the authors that the parents like congratulated themselves the farmers that the ministers admire injured herself
G Vision Pretraining Details
We pretrain a Resnet50 model and MLP using SimCLR, contrastive self-supervised learning algorithm (Chen et al. 2020). This algorithm generates two views of an image using random data augmentations, then maximizes the agreement between representations of these views using contrastive loss function. We use temperature 0.07 for this loss.
Our data augmentations include horizontal flips, affine transformations, color jitters, rotations, and grayscaling. We train for 100 epochs, using a learning rate of ,0005 (which is decayed according to a consine annealing schedule) and batch size of 256. Images are drawn randomly from the three compositional training sets Auside-Contact Number-Contact, Inside-Number). For every rule-following image that is selected, rule-breaking image from that same dataset is also selected.
We evaluate the Top-5 Accuracy held-out validation set after every epoch, and save the weights of the best performing model. Following Chen et al.] (2020), we discard the MLP after pretraining, only using the Resnet50 weights initialize our pretrained models in Section g
We adapted the implementation found
Lippe (222) implement SimCLR pretraining.
H Subnetwork Sparsity Data
In this section, we provide the raw sparsity statistics for each subnetwork trained in this paper. For every subnetwork, we indicate what stage we started masking (0, 3, or 4), provide the number of Act. Param. in the subnetwork (i.c. the number of 1 Is in the binary mask), and include the total number of parameters that we mask over (i.e. the number entries in the binary mask), which determined by the mask stage.
I Control Experiment: Random Models
Recent work has demonstrated several surprising properties of masks trained on randomly-intaalzed networks (Ramanujan al. 2020; Zhou et al. 2019: Wortsman et al. 2020). One might wonder whether the results demonstrated here could be obtained by training binary mask over randomly- initialized network. If so, this would pose serious problem for interpretation of the data: producing the same results in a randomly- randomly-initialize, initializze network would decouple the behavior of the discovered subnetworks from the representations learned by the underlying base model.
We carry out this experiment control. Specifically, we run the exact same mask training procedure used to generate the results in Section 7 except randomly -intiliiiii models rather than
26

---

TASK
SR
MODEL
MASK
STAGE
ACT. PARAM.
TOT. PARAM.
NUMBER-CONTACT
CONTACT
4
8059720
19398656
CONTACT
CONTACT
2
4
8200381
19398656
NUMBER- CONTACCT
CONTACT
3
4
8199621
19398656
KUMBER-CONTACT
0
259611
27911360
NUMBER- CONTACT
NUMBER-CONTAS
NUMBER
2
0
264197
27911360
AUMBER-CONTACT
NUMBER
3
0
438332
27911360
NUMBER- -ONTACT
CONTACT
1
3
996278
26476544
NUMBER-CONTE
CONTACT
2
3
1010779
26476544
NUMBER CONTACT
NUMBER-CONTACEE
CONTACT
3
3
970624
26476544
NUMBER- CONTACT
NUMBER-CONTACH
NUMBER
1
4
1831379
19398656
NUMBER
2
2
4
1822564
19398656
NUMBER-CONTACT
NUMBER
3
4
1814451
19398656
TUMBER-CONTACT
CONTACT
4
6044544
19398656
NUMBER CONTACT
NUMBER-CONTACEE
CONTACT
2
4
6111795
19398656
NUMBER-CONTAS
CONTACT
CONTACT
3
4
6258924
19398656
CIMMERR-CONTAN
NUMBER
1
0
225866
27911360
NUMBER- CONTACTT
NUMBER
2
0
685279
2791133
NUMBER
3
219003 0
27911360
INSIDE-CONTACT
INSIDE
1
4
2418223
19398656
ISIDE-CONTACT
INSIDE
2
4
2384556
19398656
INSIDE-CONTACEE
INSIDE
3
4
2307045
19398656
INSID--CONTAL
CONTACT
1
4
1029149
19398656
NSIDE-CONTACT
CONTACT
2
4
1057758
19398656
INSIDE-CONTACT
CONTACT
3
4
938794
19398656
INSIDE-CONTACT
INSIDE
1
3
189266
26476544
INSID-CONNTAE
INSIDE
2
2
3
140762
26476544
INSIE-CONTACE
INSIDE
3
3
184485
26476544
USIDE-CONTACT
CONTACT
3
1266369
26476544
INSIDE-CONTACT
CONTACT
3
1333968
26476544
INSIDE-COTACCT
CONTACT
2
3
3
1078198
26476544
NSSDE-CONTACT
INSIDE
3
1
3
94253
26476544
INSIDE-CONTACT
INSIDE
2
3
159807
26476544
INSIDE-CONTACT
INSIDE
3
3
231113
26476544
INSIDE-CONTACT
CONTACT
1
3
1681559
26476544
INSIDE-CONTACT
CONTACT
3
2
3
1684466
26476544
INSIDE-CONTACT
CONTACT
3
3
1682888
26476544
INSIDE-NUMBER
INSIDE
1
4
7004974
19398656
INSIDE-NUMBER
INSIDE
2
4
7077554
19398656
INSIDE-NUMBER
INSIDE
3
4
7077890
19398656
INSIDE NUMBER
INSIDE-NUMBER
NUMBER
1
3
3190833
26476544
INSIDE-NUMBER
NUMBER
2
3
3291780
26476544
SUIDE-NUMBER
NUMBER
3
3
3559092
26476544
INSIDE-NUMBER
INSIDE
4
5255315
19398656
INSIDE-NUME -UMBER
INSIDE
2
4
5253035
19398656
INSIDE-NUMIN
INSIDE
2
3
4
5151024
19398656
-SIDE-NUMBER
NUMBER
2
4
3149872
19398656
INSIDE-NURE SUUDE-NUMBER
NUMBER
2
4
2765010
19398656
ASIDE-NUUBER
NUMBER
3
4
2675994
19398656
INSIDE-
INSIDE-NUMBER -NMMBER
INSIDE
1
3
920241
26476544
ANSIDE-NUMBER
INSIDE
3
2
3
853147
26476544
NSIDE-NUMBER
INSIDE
3
3
974109
26476544
INSIDE-NUMBER
NUMBER
1
5033831 4
5046083
19398656
INSIDE-NUMBER
NUMBER
2
19398656
INSIDE-NUMBER
NUMBER
3
4
5086233
19398656
Table 5: Resnet50 subnetwork sparsity statistics. Act. Param. is the number of active parameters in subnetwork. Tot. Param. is the total number of parameters in the masked layers.
27

---

TASK
SR
MODEL
MASK
STAGE
ACT. PARAM.
TOT. PARAM.
NUMBER-CONTACT
CONTACT
3
1184224
26476544
CONTACT
CONTACT
2
3
875632
26476544
NUMBER- CONTACCT
CONTACT
3
3
960475
26476544
NUMBER- KUMBER-CONTACT
4
703485
19398656
NUMBER- CONTACT
NUMBER-CONTAS
NUMBER
2
4
682724
19398656
AUMBER-CONTACT
NUMBER
3
4
684961
19398656
NUMBER- -ONTACT
CONTACT
1
3
833083
26476544
NUMBER-CONTE
CONTACT
2
3
935644
26476544
NUMBER CONTACT
NUMBER-CONTACEE
CONTACT
3
3
903822
26476544
NUMBER- NUMBER-CONTACH
NUMBER
1
4
682249
19398656
NUMBER
2
2
4
660732
19398656
NUMBER-CONTACT
NUMBER
3
4
611524
19398656
TUMBER-CONTACT
CONTACT
3
898919
26476544
NUMBER CONTACT
NUMBER-CONTACEE
CONTACT
2
3
1129741
26476544
NUMBER-CONTAS
CONTACT
CONTACT
3
3
765665
26476544
NUMBER- CONTACT
NUMBER
4
8734131
19398656
NUMBER- CONTACT
NUMBER
2
4
8880893
19398656
NUMBER
3
8900554 4
19398656
INSIDE-CONTACT
INSIDE
1
4
138289
19398656
ISIDE-CONTACT
INSIDE
2
4
102788
19398656
INSIDE-CONTACEE
INSIDE
3
4
64056
19398656
INSID--CONTAL
CONTACT
1
4
687037
19398656
NSIDE-CONTACT
CONTACT
2
4
730767
19398656
INSIDE-CONTACT
CONTACT
3
4
594200
19398656
INSIDE-CONTACT
INSIDE
1
4
119585
19398656
INSIDE-CONTAL
INSIDE
2
2
4
153621
19398656
INSDE-CONTACE
INSIDE
3
4
141847
19398656
USIDE-CONTACT
CONTACT
4
880968
19398656
INSIDE-CONTACT
CONTACT
4
582672
19398656
INSIDE-COTTCCT
CONTACT
2
3
4
549542
19398656
NSSDE-CONTACT
INSIDE
3
1
4
444801
19398656
INSIDE-CONTACT
INSIDE
2
4
404687
19398656
INSIDE-CONTACT
INSIDE
3
4
388647
19398656
INSIDE-CONTACT
CONTACT
1
4
2726236
19398656
INSIDE-CONTACT
CONTACT
3
2
4
2712782
19398656
INSIDE-CONTACT
CONTACT
3
2704681 4
19398656
INSIDE-NUMBER
INSIDE
1
3
811096
26476544
INSIDE-NUMBER
INSIDE
2
3
849964
26476544
INSIDE-NUMBER
INSIDE
3
3
781551
26476544
INSIDE NUMBER
INSIDE-NUMBER
NUMBER
1
0
14878394
27911360
INSIDE-NURE -SSMBER
NUMBER
2
0
14739139
2791
SUIDE-NUMBER
NUMBER
3
0
14919954
27911360
INSIDE-NUMBER
INSIDE
4
375073
19398656
INSIDE-NUME -UMBER
INSIDE
2
4
306550
19398656
INSIDE-NUMIN
INSIDE
2
3
4
314610
19398656
NNSDE-NUMBER
NUMBER
2
3
2468331
26476544
INSIDE-NURE SUUDE-NUMBER
NUMBER
2
3
3106382
26476544
ASIDE-NNUBER
NUMBER
3
3
3122791
26476544
INSIDE-NUMEN -NMMBER
INSIDE
1
0
660344
27911360
ANSIDE-NUMBER
INSIDE
3
2
0
714676
27911360
NSIDE-NUMBER
INSIDE
3
0
692889
27911360
INSIDE-NUMBER
NUMBER
1
3
3369673
26476544
INSIDE-NUMBER
NUMBER
2
3
3661479
26476544
INSIDE-NUMBER
NUMBER
3
3
3278225
26476544
Table 6: Resnet50 + SimCLR Subnetwork sparsity statistics. Act. Param. is the number active parameters in subnetwork. Tot. Param. is the total number of parameters in the masked layers.
28

---

TASK
SR
MODEL
MASK
STAGE
ACT. PARAM.
TOT. PARAM.
NUMBER-CONTACT
CONTACT
4
12415313
46399488
NUMBER- CONTACT
CONTACT
2
4
1 11886093
46399488
NUMBER- CONTACCT
CONTACT
3
4
11994752
46399488
NUMBER- KUMBER-CONTACT
0
364048
71222464
NUMBER- CONTACT
NUMBER-CONTAS
NUMBER
2
0
356776
71222464
AUMBER-CONTACT
NUMBER
3
0
430018
71222464
NUMBER- -ONTACT
CONTACT
1
4
8156499
46399488
NUMBER-CONTE
CONTACT
2
4
8188321
46399488
NUMBER CONTACT
NUMBER-CONTACEE
CONTACT
3
4
8730014
46399488
NUMBER- NUMBER-CONTACH
NUMBER
1
0
489546
71222464
NUMBER
2
2
0
479722
71222464
NUMBER-CONTACT
NUMBER
3
0
405563
71222464
TUMBER-CONTACT
CONTACT
4
11238193
46399488
NUMBER CONTACT
NUMBER-CONTACEE
CONTACT
2
4
11246123
46399488
NUMBER CONTAAC
CONTACT
3
3
4
11084672
46399488
CIMMERR-CONTAN
NUMBER
4
792483
46399488
HIMBER--CONTACE
NUMBER
2
4
681226
46399488
NUMBER
3
834326 4
46399488
INSIDE-CONTACT
INSIDE
1
3
177339
67108864
ISIDE-CONTACT
INSIDE
2
3
147071
67108864
INSIDE-CONTACEE
INSIDE
3
3
232306
67108864
INSID--CONTAL
CONTACT
1
3
1 1100205
67108864
NSIDE-CONTACT
CONTACT
2
3
966156
67108864
INSIDE-CONTACT
CONTACT
3
3
1043718
67108864
INSIDE-CONTACT
INSIDE
1
0
875532
71222464
INSIDE
2
2
0
493009
71222464
USIDE-CONTACT
INSIDE
3
0
619362
71222464
USIDE-CONTACT
CONTACT
3
5898635
67108864
INSIDE-CONTACT
CONTACT
3
6213208
67108864
INSIDE-COTTCCT
CONTACT
2
3
3
5909038
67108864
NSSDE-CONTACT
INSIDE
3
1
3
557265
67108864
INSIDE-CONTACT
INSIDE
2
3
330289
67108864
INSIDE-CONTACT
INSIDE
3
3
710769
67108864
INSIDE-CONTACT
CONTACT
1
3
4632439
67108864
INSIDE-CONTACT
CONTACT
3
2
3
4376935
67108864
INSIDE-CONTACT
CONTACT
3
3
4964646 3
67108864
INSIDE-NUMBER
INSIDE
1
3
208 0081068
67108864
INSIDE-NUMBER
INSIDE
2
3
2106222
67108864
INSIDE-NUMBER
INSIDE
3
3
2007091
67108864
INSIDE NUMBER
INSIDE-NUMBER
NUMBER
1
4
3541726
46399488
INSIDE-NURE -UUDERR
NUMBER
2
4
3560812
46399488
SUIDE-NUMBER
NUMBER
3
4
3583605
46399488
INSIDE-NUMBER
INSIDE
0
2242819
71222464
INSIDE-NUME -UMBER
INSIDE
2
0
1963701
71222464
INSIDE-NUMIN
INSIDE
2
3
0
1330134
71222464
NNIDE-NUMBER
NUMBER
2
3
5749408
67108864
INSIDE-NURE SUUDE-NUMBER
NUMBER
2
3
5511381
67108864
USIDE-NNMBER
NUMBER
3
3
5472792
67108864
INSIDE-
INSIDE-NUMBER -UMBER
INSIDE
1
0
808884
71222464
ANSIDE-NUMBER
INSIDE
3
2
0
851288
71222464
NSIDE-NUMBER
INSIDE
3
3
0
731729
71222464
INSIDE-NUMBER
NUMBER
1
0
3487441
71222464
INSIDE-NUMBER
NUMBER
2
0
3528010
71222464
INSIDE-NUMBER
NUMBER
3
0
4330284
71222464
Table 7: Wide Resnet50 Subnetwork sparsity statistics. Act. Param. is the number of active parameters in subnetwork. Tot. Param. is the total number of parameters in the masked layers.
29

---

TASK
SR
MODEL #
MASK
STAGE
ACT. PARAM.
TOr. PARAM.
(S) SV AGREEMENT
SUBJECT
0
1246922
12845056
(S) SV AGREEMENT
SUBJECT
2
0
1242347
12845056
(S) SV AGREEMENT
SUBJECT
3
0
2128824
12845056
(S) SV AGREEMENT
VERB
0
1668369
12845056
(S) SV AGREEMENT
VERB
2
0
2600240
12845056
(S) SV AGREEMENT
VERB
3
0
3353398
12845056
(S) SV AGREEMENT
SUBJECT
0
2728632
12845056
SV AGREEMENT
SUBJECT
0
2663842
12845056
(S) SV AGREEMENT
SUBJECT
3
0
2681724
12845056
(S) SV AGREEMENT
VERB
0
951132
12845056
(S) SV AGREEMENT
VERB
2
2
0
1044003
12845056
(S) SV AGREEMENT
VERB
3
0
1084848
12845056
(S) SV AGREEMENT
SUBJECT
328484
12845056
(S) SV AGREEMENT
SUBJECT
2
0
720899
12845056
(S) SV AGREEMENT
SUBJECT
3
3
0
323764
12845056
(S) SV AGREEMENT
VERB
3
3
1794939
6553600
SV AGREEMENT
VERB
2
3
1702597
6553600
(S) SV AGREEMENT
VERB
3
3
1567156
6553600
(P) SV AGREEMENT
SUBJECT
0
69748
12845056
(P) SV AGREEMENT
SUBJECT
2
0
68641
12845056
(P) SV AGREEMENT
SUBJECT
3
0
52336
12845056
(P) SV AGREEMENT
VERB
1
3
640889
6553600
(P) SV AGREEMENT
VERB
2
3
477101
6553600
(P) SV AGREEMENT
VERB
3
3
656202
6553600
(P) SV AGRREMENT
SUBJECT
0
119037
12845056
(P) SV AGREEMENT
SUBJECT
2
0
125594
12845056
(P) SV AGREEMENT
SUBJECT
3
0
122828
12845056
(P) SV AGREEMENT
VERB
215555
12845056
(P) SV AGREEMENT
VERB
2
202185
12845056
(P) SV AGREEMENT
VERB
3
0
56134
12845056
(P) SV AGREEMENT
SUBJECT
3
0
86084
12845056
(P) SV AGREEMENT
SUBJECT
2
0
49694
12845056
(P) SV AGREEMENT
SUBJECT
3
166614
12845056
(P) SV AGREEMENT
VERB
3
1
0
149398
12845056
(P) SV AGREEMENT
VERB
3
2
0
221074
12845056
(P) SV AGREEMENT
VERB
3
0
133149
12845056
Table 8: BERT Subject-Vert Agreement Subnetwork sparsity statistics. Act. Param. is the number of active parameters in subnetwork. Tot. Param. the total number of parameters the masked layers.
models trained on compositional tasks. In Section 7 each (model, subroutine) pair had its own set of masking hyperparameters. We use these same hyperparameters for each (randomly-intialize model, subroutine) pair in order to make the results as comparable as possible.
In Figure T6 and 17 we observe that masking random networks produces distinctly different patterns of results than we presented in Section 7 Though possible find a subnetwork that computes a target subroutine and not the other subroutine, the ablation results do not follow the pattern that one would expect of compositional model. This accords with Ramanujan al. (2020), which demonstrates that training binary mask over a randomly-weighter network can still produce performant subnetworks. The ablation results indicate that these subnetworks are causally implicated in model behavior. In the case of Resnet50 (Figure [6] Bottom) we observe that ablating the learned subnetworks collapses performance chance for all tasks. the case of BERT-Small (Figure 17, Bottom), we observe that ablating the learned subnetworks oftentimes yields high performance on Test Target Subroutine and low performance on Test Other Subroutine, which the opposite of the expected trend for compositional model. Thus, we can be more confident that
30

---

TASK
SR
MODEL #
MASK #
STAGE
ACT. PARAM.
TOT. PARAM.
(S) ANAPHORA
PRONOUN
0
370568
12845056
(S) ANAPHORA
PRONOUN
2
0
372203
12845056
(S) ANAPHORA
PRONOUN
3
0
369123
12845056
(S) ANAPHORA
ANTECEDENT
I
169120
12845056
(S) ANAPHORA
ANTECEDENT
2
0
150554
12845056
(S) ANAPHORA
ANTECEDENT
3
0
231819
12845056
(S) ANAPHORA
PRONOUN
2
1
0
968021
12845056
(S) ANAPHORA
PRONOUN
2
971063
12845056
(S) ANAPHORA
PRONOUN
3
970910
12845056
(S) ANAPHORA
ANTECEDENT
2
1
0
108544
12845056
(S) ANAPHORA
ANTECEDENT
2
2
0
1 110871
12845056
(S) ANAPHORA
ANTECEDENT
3
108347
12845056
(S) ANAPHORA
PRONOUN
79069
12845056
(S) ANAPHORA
PRONOUN
3
2
0
79031
12845056
(S) ANAPHORA
PRONOUN
3
3
0
82788
12845056
(S) ANAPHORA
ANTECEDENT
1
1854552
12845056
(S) ANAPHORA
ANTECEDENT
2
1848327
12845056
(S) ANAPHORA
ANTECEDENT
0
1874968
12845056
(P) ANAPHORA
PRONOUN
1
0
325597
12845056
(P) ANAPHORA
PRONOUN
2
0
417498
12845056
(P) ANAPHORA
PRONOUN
3
0
642805
12845056
(P) ANAPHORA
ANTECEDENT
0
286739
12845056
ANAPHORA
ANTECEDENT
2
0
336572
12845056
(P) ANAPHORA
ANTECEDENT
3
0
405887
12845056
(P) ANAPHORA
PRONOUN
2
1
0
24818
12845056
(P) ANAPHORA
PRONOUN
2
2
0
24805
12845056
(P) ANAPHORA
PRONOUN
3
0
24855
12845056
(P) ANAPHORA
ANTECEDENT
1
3
1154161
6553600
(P) ANAPHORA
ANTECEDENT
2
3
1183436
6553600
(P) ANAPHORA
ANTECEDENT
2
3
3
1159462
6553600
(P) ANAPHORA
PRONOUN
3
1
0
144186
12845056
(P) ANAPHORA
PRONOUN
2
0
151531
12845056
(P) ANAPHORA
PRONOUN
0
153897
12845056
(P) ANAPHORA
ANTECEDENT
3
1
0
4606842
12845056
(P) ANAPHORA
ANTECEDENT
3
2
5134758
12845056
(P) ANAPHORA
ANTECEDENT
3
504 5841888
12845056
Table 9: BERT Anaphora Subnetwork sparsity statistics. Act. Param. is the number of active parameters subnetwork. Tot. Param. the total number of parameters in the masked layers.
the main results presented in Section 7 reflect the internal mechanisms of trained models, and are not epiphenomenal artifacts training binary masks over networks.
I.1 Statistical Analysis Main Results vs. Random Results
In order to assess whether the results given by random models are significantly different from our main results,
generalized linear model (GLM) with robust clustered standard errors for each combination of model architecture, compositional task, and subroutine. This GLM includes dummy variable indicating whether the results from subnetwork or an ablated model, dummy variable indicating whether the base model is trained or random, and it clusters observations by base model. For language experiments, we collapse across singular and plural instances of the same subroutine. The coefficient of the Trained vs. Random dummy variable in this model assesses whether the performance the discovered subnetworks are significantly different in the trained and random conditions. From this model, we can also perform linear hypothesis test to assess whether ablated model performance is significantly different between the trained and random conditions, Table T2 provides the relevant statistics. Across the board, we see that there is often significant difference
31

---

TASK
SR
MODEL #
MASK
STAGE
ACT. PARAM.
TOr. PARAM.
(S) SV AGREEMENT
SUBJECT
0
59736
12845056
(S) SV AGREEMENT
SUBJECT
2
0
839770
12845056
(S) SV AGREEMENT
SUBJECT
3
0
620869
12845056
(S) SV AGREEMENT
VERB
3
65229
6553600
(S) SV AGREEMENT
VERB
2
3
65356
6553600
(S) SV AGREEMENT
VERB
3
3
65220
6553600
(S) SV AGREEMENT
SUBJECT
0
511359
12845056
SV AGREEMENT
SUBJECT
0
70725
12845056
(S) SV AGREEMENT
SUBJECT
3
0
555174
12845056
(S) SV AGREEMENT
VERB
0
16940
12845056
(S) SV AGREEMENT
VERB
2
2
0
39218
12845056
(S) SV AGREEMENT
VERB
3
0
19321
12845056
(S) SV AGREEMENT
SUBJECT
8514
12845056
(S) SV AGREEMENT
SUBJECT
2
0
8613
12845056
(S) SV AGREEMENT
SUBJECT
3
3
0
8593
12845056
(S) SV AGREEMENT
VERB
3
3
64969
6553600
SV AGREEMENT
VERB
2
3
65098
6553600
(S) SV AGREEMENT
VERB
3
64955 3
6553600
(P) SV AGREEMENT
SUBJECT
0
45792
12845056
(P) SV AGREEMENT
SUBJECT
2
0
45527
12845056
(P) SV AGREEMENT
SUBJECT
3
0
45616
12845056
(P) SV AGREEMENT
VERB
0
16800
12845056
(P) SV AGREEMENT
VERB
2
0
24013
12845056
(P) SV AGREEMENT
VERB
3
0
23988
12845056
(P) SV AGRREMENT
SUBJECT
0
47651
12845056
(P) SV AGREEMENT
SUBJECT
2
0
47502
12845056
(P) SV AGREEMENT
SUBJECT
3
0
47811
12845056
(P) SV AGREEMENT
VERB
3
100005
6553600
(P) SV AGREEMENT
VERB
2
3
100100
6553600
(P) SV AGREEMENT
VERB
3
3
100029
6553600
(P) SV AGREEMENT
SUBJECT
1
3
81133
6553600
(P) SV AGREEMENT
SUBJECT
2
81203 3
6553600
(P) SV AGREEMENT
SUBJECT
3
3
81218
6553600
(P) SV AGREEMENT
VERB
3
1
0
15302
12845056
(P) SV AGREEMENT
VERB
3
2
0
9423
12845056
(P) SV AGREEMENT
VERB
3
0
15900
12845056
Table 10: BERT LM Subject- Verb Agreement Subnetwork sparsity statistics. Act. Param. is the
number of active parameters subnetwork. Tot. Param. the total number of parameters in masked layers.
between ablating the discovered subnetworks in random trained models, even with small sample size.
Pruned Model Analysis
In this section, we analyze the structural compositionality models after they have been pruned. We analyze the impact of pruning structural compositionality on Resnet50 models trained on Number- Contact. We use continuous sparsification to train binary masks over the three Humber-Contanl Resnet50 models analyzed in the main paper, resulting in three sparse models that perform well on the Number-Contact task. We search over mask initialization and learning rate hyperparameters to find the best pruning configuration for each model. Then, we run the same structural compositionality analysis deseribed in the main paper. We see from Figure [8 that the results on the pruned Resnet50) models closely resemble those from the full Resnet50 models.
32

---

TASK
SR
MODEL
MASK
STAGE
ACT. PARAM.
TOT. PARAM.
(S) ANAPHORA
PRONOUN
1
0
6590452
12845056
(S) ANAPHORA
PRONOUN
2
0
6702195
12845056
(S) ANAPHORA
PRONOUN
3
0
6519670
12845056
(S) ANAPHORA
ANTECEDENT
I
0
832044
12845056
(S) ANAPHORA
ANTECEDENT
2
833149
12845056
(S) ANAPHORA
ANTECEDENT
3
0
835278
12845056
(S) ANAPHORA
PRONOUN
2
1
3
193677
6553600
(S) ANAPHORA
PRONOUN
2
2
3
198612
6553600
(S) ANAPHORA
PRONOUN
3
3
198956
6553600
(S) ANAPHORA
ANTECEDENT
1
0
39355
12845056
(S) ANAPHORA
ANTECEDENT
2
2
0
27784
12845056
(S) ANAPHORA
ANTECEDENT
2
3
0
34674
12845056
(S) ANAPHORA
PRONOUN
36495
12845056
(S) ANAPHORA
PRONOUN
2
1458843
12845056
(S) ANAPHORA
PRONOUN
3
3
75100
12845056
(S) ANAPHORA
ANTECEDENT
3
1
0
648936
12845056
(S) ANAPHORA
ANTECEDENT
2
680218
12845056
(S) ANAPHORA
ANTECEDENT
3
0
760770
12845056
(P) ANAPHORA
PRONOUN
1
0
11374
12845056
(P) ANAPHORA
PRONOUN
2
11251
12845056
(P) ANAPHORA
PRONOUN
3
0
11369
12845056
(P) ANAPHORA
ANTECEDENT
1
0
1152444
12845056
(P) ANAPHORA
ANTECEDENT
2
0
115251 18
12845056
(P) ANAPHORA
ANTECEDENT
3
1149693
12845056
(P) ANAPHORA
PRONOUN
11327
12845056
(P) ANAPHORA
PRONOUN
2
2
0
11321
12845056
(P) ANAPHORA
PRONOUN
2
3
0
11275
12845056
(P) ANAPHORA
ANTECEDENT
43274
12845056
(P) ANAPHORA
ANTECEDENT
2
44220
12845056
(P) ANAPHORA
ANTECEDENT
2
3
0
45632
12845056
(P) ANAPHORA
PRONOUN
3
1
0
28866
12845056
(P) ANAPHORA
PRONOUN
3
2
0
28887
12845056
ANAPHORA
PRONOUN
3
29101
12845056
(P) ANAPHORA
ANTECEDENT
0
4292104
12845056
(P) ANAPHORA
ANTECEDENT
3
2
4350952
12845056
(P) ANAPHORA
ANTECEDENT
3
3
0
4048117
12845056
Table 11: BERT + LM Anaphora Subnetwork sparsity statistics. Act. Param. is the number of active
parameters subnetwork. Tot. Param. is the total number of parameters in the masked layers.
COMP. TASK
MODEL
SR
RANDOM COFF,
LINEAR HYPOTHESIS X²
IN. CONT.
RN50
INSIDE
-1.36
2.44
IN. CONT.
RN50
CONTACT
-1.73.
1.17
IN. NUM.
RN50
INSIDE
-1.92.
29.20***
NUM.
RN
NUMBER
-1.41
48.95***
CONT. NUM.
RN50
CONTACT
-0,51
57.47**#
CONT. NUM.
RN50
NUMBER
-0.26
0.54
SV AGR
BERT
SUBJ.
2.13*
19, 17.
SV AGR
BERT
VERB
2.61 8*
70.08***
ANAPHORA
BERT
PRONOUN
2.46
222.64***
ANAPHORA
BERT
ANTECEDENT
0.24
17.87**
Table 12: Statistics from two factor GLM with robust clustered standard errors. indicates significance
at = .1, indicates significance at .05, *s indicates significance at _01, *** indicates significance at .001
33

---

Inside Contect
Inside Number
Number-Contee
1.00
673
0.5
47-
630
033
032
0.50
0.50
3.50
023
0:33
033
029
325
3.25
Contact
-32
S.lmowook
Sclmtwork Ablation
Scbmiweak
S.bratwork
Alfecim
Resnet50 Subnetworks: InsieeCContac
Resme:50 Subnetworks:
Inside Number
Resnet50 Submetworks.
Number-Conted
033
Contact
Other
Resnet50 Ablated Networks: Inside-Contact
Resnet50 Ablated Networks: Inside-Number
Resnet50 Ablated Networks: Number-Contact
3.-
0.5
Contect
Tbrget
Oeher
Torget
Other
Thiggt
Other
Target
Other
T5rget
Other
Target
Other
Figure 16: Results from training masks over randomly-initialized Resnet50. (Top) Plots displaying differences in performance. (Middle) Plots displaying subnetwork performance on each task. (Bottom) Plots displaying ablated model performance each task. Across the board, we see that masks over random networks can produce subnetworks that achieve better accuracy on on Test Target Subroutine than on Test Other Subroutine, but that ablating these subnetworks results in (equally) poor performance on both of these datasets.
K Subnetwork Overlap Analysis
In this section, we analyze the overlap in the subnetworks that were discovered within the same base model. We perform this analysis one model, Resnet50 trained the Inside-Number task. From Figure 4 we see that this model appears to exhibit structural compositionality. model because subnetwork masking started at the same layer for both subroutines, which allows for straightforward comparison of the overlap between subnetworks. All results are shown in Figure 19
analyze this
Following previous work (Csordás et al. 2021), we compute the per-layer intersection over union (IoU) quanitify subnetwork overlap. First, we do this for each of the three subnetworks discovered for the Inside subroutine. See these results in Table 13 Next, we compute the same for the three subnetworks discovered for the Number subroutine. See these results in Table The Inside subroutine gives near ceiling agreement, while the Number task exhibits much lower agreement. This indicates that the subnetworks we uncover are somewhat noisy for the Number subroutine, but not for the Inside subroutine. Finally, we compute the intersection of each set of subnetworks, and compute the per-layer intersection over union between tasks. See Table [5] We see very low agreement between tasks, especially before the final MLP. Notably, this between-task agreement is consistently
34

---

Anaphora
SV Agreement
1.00
1.00
0.75
0.75
0.75
0.75
8
fromoun
025
Antecedentt
0.5
Subject
0.25
0.25
Verb
-0.25
-0.50
-0.30
-0.50
-0.50
-1.00
-.00 Subnelwork
-1.00
-1.00
Subnetwork
Ablation
Ablation
Subnelwork
Ablation
Subnetwork
Ablation
BERT Small Subnetworks: Anaphora
BERT Small Subnetworks: SV Agreement
8*A
0.8
Antecedent
Fronoun
0.6
0.4
Subject
Werb
0.6
0.4
0.4
0.4
$o
0.2
0.2
02
0.2
0.0
0.0
0.0
Target
Other
Target
Other
Target
Other
Target
Other
BERT Small Ablated Networkss: Anaphora
BERT Small Ablated Networks: SV Agreement
S A
Intecedeent
Pronoun
Subject
Verbi
812
0.2
u.2
0.7
0.2
0.0
0.0
0.0
0.0
Target
Other
Target
Other
Target
Other
Target
Other
Figure 17: Results from training masks over a randomly-initialized BERT-Small. (Top) Plots displaying differences in performance. (Middle) Plots displaying subnetwork performance each task. (Bottom) Plots displaying ablated model performance on each task. Across the board, we see that masks over random networks can produce subnetworks that achieve better accuracy on Test Target Subroutine than on Test Other Subroutine. Surprisingly, ablating these subnetworks still results in better accuracy on on Test Target Subroutine than Test Other Subroutine.
lower than both within-tate task agreement values for each layer. This reinforces our interpretation that these subnetworks are organized in modular fashion within the base models.
35

---

LAYER
IoU
BACKBONE, WWW.LA...CR.OOOO...
0.974
JACKBONE.LAYER WWW.VEE....CCON... 0.CONV2
0.963
BACKBONE.LAYERS
WAW.RA...EEEENNEEEEE.. 0.CONV3
0.971
0.971
JACKBONE.LAYERS LAYEE4...CONNY 1.CONV
0.970
BACKRONE.LAYERS 1.COV2
0,960
JACKRONE.LAYERR 1.CONV3
0.969
BACKBONE, LAYER.....LYYRR2...OO
0.975
BACKBONE, BOCKKBON..LYYRR.2222. LAYER4.2.CONV2
0.971
BACKBONE, BACKBONE.LAVER4.22 LAYER4.2.CONV3
0,970
MLP.MODEL.0
0,994
MLP.MODEL.2
0.989
Table 13: IoU computed over the three discovered subnetworks in for the Inside subroutine
LAYER
IOU
EERKBONE.LAYERR 0.CONV1
0.370
LAYER 4.0CEV,
0.236
BACKBONE. LAYER.....YY....C...O ..0.covV33
0.264
BACKBONE.LAVERS 0.DONNSAMPLE.
0.257
MACKBONE.LAYERS 1.COVV
0.287
SICKBONE.LAYERS WWW.A......CO.. 1.COV22
0,208
BACKBONE.LAYER4 I.CONV3
0.218
LAYER4.
0.197
JICKBOON.LLAVRR..222..
0.129
BACKRONE.LAYER A.YR4......
0.162
MI.. M.P.MODEL..) MLP.MODEL.2
0.516
0.411
Table 14: IoU computed over the three discovered subnetworks in for the Number subroutine
LAYER
loU
BACKBONE 00.OOV
0.122
BACKBONE, LAY.E..................O... C.
0.062
0.087
LAYER O.DOOSSSAPPEE
0.057
BACKBONE.LAYERS 1.COVV1
0.070
BACKBONE.LAYERS 1.CONV2
0.054
LAYER4.
0.076
L.CEEBON..LYYER.2..CO
0.034
BACKBONE, BICKBOON.LAYER4..22 LAYER4.2.CON2
0.027
LACKBONE.LVEER.22.cO
0,055
MLP.MODEL.0
0,237
MLP. M.D.MODEL.2
0.321
Table 15: IoU computed over the intersections of the subnetworks discovered for each task.
36

---

Pruned Resnet50 (Test Target Test Other)
Number-Contact
1.00
1.00
0.75
0.75
0.50
0.50
0.25
0.25
Contact
Number
0.00
0.00
-025
-0.25
-0.50
0.50
-0.75
-0.75
-1.00
-1.00
Subnetwork Ablation
Subnetwork Ablation
Figure 18: Structural compositionality analysis using pruned Resnet50 models on the Number- Contact task. We that these results closely match those found in the main paper.
37

---

Overlap Analysis
1.0
0.8
leu
0.4
02
Number
Intersection
barktone layeraaa.coomm c.c.c.v
backbone layert conv2
backbone layerd, 1. Lcoov2
backbone lnyor4, L.com22
backbooe layerd 4.2 convi
backbone layert conv2
backbone layer 2.como3
mip model.0-
mip model.2
backhone..co layer4,, d.doonsamppee...
backbone layor4,
backbone
Layers
Figure 19: The results of subnetwork overlap analysis for one base model trained on the Inside- Number task. These results show that within-task subnetwork overlap is substantially higher than between-task subnetwork overlap. measured by intersection over union (IoU), Within task, we are computing the loU between 3 subnetworks trained for that task. Between tasks, we first take the intersection of all 3 subnetworks trained for each task, and then compute the IoU of the intersections.
38


Reviews:
[{"review_id": "lNAwynclOI", "reviewer": "Reviewer_xQUi", "summary": "The authors investigated to what extent the standard neural networks of the present day trained on the tasks solvable by composing subroutines result in modular structures reflecting the tasks' compositional nature (called structural compositionality in this study). To answer this question, they took the following approach on the trained networks: 1) use a model pruning technique to find the best subnetworks for individual subroutines, then 2) check the patterns in  accuracy difference of the discovered subnetworks and the ablated networks (complemental subnetworks with respect to the first ones) on the tasks corresponding to individual subroutines. They conducted experiments on both vision and language tasks with multiple neural networks and pretraining regimes. Based on the results, they concluded that the neural networks oftentimes exhibit structural compositionality even when there are no explicit inductive biases toward such solutions.", "questions": "Major Suggestions \n1. I suggest adding README explaining the overall repository in the top-level directory during the Author Rebuttal period.\n1. I suggest better contextualizing this work with respect to Csordás et al. 2021 in the paper.\n\nPlease also refer to Weaknesses section above.\n\nMinor Sugestions \n1. It would be better to mention WideResNet in Section 7 (Results) and point to Appendix.\n1. It would be nice if applicability of the proposed approach to recurrent neural networks are explained in the paper. \n\n\n", "limitations": "The authors describes the limitations of their current method and the results reported in the paper in Section 10 (Discussion):  \n1. Their current method requires one to specify which subroutines to look for in advance. \n1. Their current method requires one to use causal ablations and control models to properly interpret. \n1. The reported results do not contain any analysis on the relationship between structural compositionality and compositional generalization.\n\n\\# Personally, I am very interested in 3, which is fully left for the future work.   \n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Making a learning machine that has compositional (systematic) generalization capability like a human is an important goal yet to be achieved in the field of artificial intelligence. On one hand, standard neural networks that are not explicitly imposed inductive biases for compositionality can generally be said to fail in compositional generalization as stated in lines 56 - 57, but on the other hand, these networks show compositional generalization capability to some extent in some cases, although not perfect and inferior to the ones that are imposed inductive biases. Revealing what is going on inside a neural network is an important research topic in this context, and the approach and results of this study will be of interest to the NeurIPS audience. \n\nThe idea of the approach took in this study is clear and reasonable. The model pruning method, experimental logic and concrete experiments are explained fairly well (some part is given in the Appendix).  The experiments are fairly rich in terms of tasks (both vision and language tasks were conducted and there are varieties in each) and models (ResNet50, WideResNet50, and ViT were tried for visual tasks, and BERT-small was tried for language tasks). \n ", "weaknesses": "1. The URL of an Anonymous GitHub repository is provided in the paper (footnote on page 2, https://anonymous.4open.science/r/Compositional_Subnetworks-C8AB/). However, it is very hard to access the contents of the repo, because, although the repo consists of many subdirectories, there is no README in the top-level directory giving an overview.  This cast a shadow on the reproducibility.  \n1. Another relatively weak point of this paper is the contextualization relative to Csordás et al. 2021. In lines 49 and 259, Csordás et al. 2021 is explained as a work merely on a multitask setting, but it studied compositional (systematic) generalization settings using the SCAN (Lake and Baroni 2018) and the Mathematics Dataset (Saxton et al. 2019). \n\n\n\nCsordás, R., van Steenkiste, S., and Schmidhuber, J. Are neural nets modular? Inspecting functional modularity through differentiable weight masks. In Proc. of the 9th International Conference on Learning Representations (ICLR), 2021. \n\nLake, B. M.  and Baroni, M. Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks. In Proc. of the 35th International Conference on Machine Learning (ICML), pp. 2873--2882, 2018. \n\nSaxton, D., Grefenstette, E., Hill, F., and Kohli, . Analysing mathematical reasoning abilities of neural models. In Proc. of the 7th International Conference on Learning Representations (ICLR), 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your excellent feedback on our work! We have updated the README in the anonymous repository. We agree that it is valuable to add an extended discussion of Csordas et al. 2021 in this paper, and we will include a full paragraph in our related work section to elaborate on the relationship between our contribution and theirs. In particular, we will note how their work convincingly demonstrates that the same underlying algorithm is not being used in different data partitions, which implies that the network is behaving non-compositionally. One interesting difference between their study and ours is that our study explicitly looks for the compositional subroutines that a model might be implementing, whereas Csordas et al. looks for subnetworks that solve subsets of the dataset. Also, we will certainly comment on the WideResNet results in the main body, thanks for pointing that out! "}, {"review_id": "w0Au0xEzpR", "reviewer": "Reviewer_W9E9", "summary": "This research paper explores the concept of compositionality in neural networks, a contentious topic in the field of AI. Compositionality, which is a defining feature of human cognition, allows for abstract and flexible processing of language and visuals. The debate lies in whether neural networks need explicit symbolic systems to implement compositional solutions, or if these solutions can be implicitly learned during training. This research introduces \"structural compositionality\", which gauges the degree to which neural networks can break down compositional tasks into subroutines and implement them in a modular fashion. Surprisingly, the study found evidence that many models do implement subroutines in modular subnetworks. Additionally, it was found that unsupervised pretraining leads to a more consistently compositional structure in language models. This research contributes to mechanistic interpretability, helping explain the algorithms that neural networks implement in their weights, using techniques from model pruning.", "questions": "A question for the authors to think about: what is the role of pruning (or network density, more generally) in the emergence of structural compositionality? Would you expect that emergence to be equally likely in a dense network and in a sparse network that has resulted through  pruning?\n\nAnother question to think about: what is the role of the network's depth in the emergence of structural compositionality? Functional compositionality can have its own depth. How is that functional depth relate to the depth of the network itself?", "limitations": "The paper is honest about its limitations. The important of them is that one has to know in advance which \"subroutines\" (I do not like this term actually -- maybe \"concepts\" or \"subfunctions\" would be better terns) to look for. This limitation however may be addressed by other work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper is quite interesting, timely and I think that most people would find the results surprising. The area of mechanistic interpretability is very important these days. One of the strongest points of this paper is the elegant approach it is taking, in terms of experimental design, to construct compositional tasks and to discover whether the presence of such \"functional compositionality\" also results in specific subnetworks for each \"concept\". The paper presents results both for images and for language experiments. The results are clear and the presentation of the paper is very good.", "weaknesses": "Of course, one general weakness is that the main result of the paper is through empirical results. The reader may not be convinced whether the claims of the paper are actually true in general -- or whether they are true only in some architectures and tasks. \n\nAnother major weakness, which the authors also identify as a limitation of their study, is that the one must know which subroutines to look for.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your excellent feedback and questions about our work! We agree that the current work is a purely empirical study, and so we attempted to demonstrate the effect on various architectures and domains to help convince the reader that structural compositionality is a property of a wide class of models. That said, since submitting (and even more so after your comments), we have been investigating possible theoretical work that might relate to our findings. Particularly interesting is this recent paper on compositionality and sparse representations in neural networks (Poggio 2023, https://cbmm.mit.edu/sites/default/files/publications/Theoretical_Framework__How_Deep_Nets_May_Work_24.pdf). We will add a new section to our discussion to outline the ways in which our results are consistent with such theoretical work, and point towards possible future experiments that could better connect the two.\n\nYour question regarding how sparsity interacts with structural compositionality is very interesting! We will run an experiment during the discussion period to investigate this, and update leave a comment on OpenReview with the results next week. We will also add these results to the Appendix.\n"}, {"review_id": "jzMGWayjf8", "reviewer": "Reviewer_oWEk", "summary": "The paper investigates the concept of structural compositionality in neural networks - subnetworks that implement specific subroutines, such as computing the syntactic number of specific words in a sentence. ", "questions": "**Important Related Work:** While the authors mention the field of mechanistic interpretability, they fail to mention some key papers in this field that explore similar ideas as the authors Chugtai et al [1] reverse engineer small neural networks to show that they learn to implement group compositions for any finite group using partical novel algorithm predicted from theory. Nouha et al [2] show that transformers solve compositional tasks by approximating part of the full computational graph as linear sub-graph matching, and provide theoretical proofs on how increasing compositional task complexity would lead to degradation in performance. I think these papers should be referred so that readers will have a more complete picture of compositionality in neural networks. \n\n### References \n\n1. Chughtai, Bilal, Lawrence Chan, and Neel Nanda. \"A Toy Model of Universality: Reverse Engineering how Networks Learn Group Operations.\" (2023).\n2. Dziri, Nouha, et al. \"Faith and Fate: Limits of Transformers on Compositionality.\" arXiv preprint arXiv:2305.18654 (2023).", "limitations": "The authors do a good job at highlighting the limitations (e.g. specifying subroutines in advance) of their work. I do not particularly see potential negative social impacts of this work as it mostly pertains to explainability of models.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. Conceptual modularity in neural networks has been an idea that has been studied and structurally implemented across various domains: explainability, reasoning, efficiency. The authors advance the field of study of modularity in neural networks by proposing the idea of structural compositionality, which is both is very well thought out and explained. The experimental plan is also carefully controlled to ensure causal observations regarding the existence of structural compositionality in networks across both vision and language tasks. Overall this is a very well done study.", "weaknesses": "No major waknesses in my opinion", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments on our work! The related works that you’ve referenced are extremely interesting, and will strengthen our discussion - thanks for pointing them out! We will add a new section to our discussion that describes the relationship between structural compositionality and the forms of compositionality that are discussed in these papers."}, {"review_id": "TMN56E6EpC", "reviewer": "Reviewer_DSTn", "summary": "This paper studies the structural compositional problem is a novel perspective. It first defines structural compositionality as the extent to which neural networks decompose a complex task into a series of subroutines and implement them modularly. Then, the paper designs several clever experiments to show that many models indeed implement subroutines in their subnetworks, which demystifies how the compositional generalization ability might occur in deep neural networks. Although the paper could be further improved in the following directions (see the limitation part), I think the current version already meets the criteria of NeurIPS and can inspire the community a lot. So I would give an accepting score to the current version. In summary, the paper is easy to follow and quite novel to me. I enjoy reading it a lot.", "questions": "1. For the non-compositional solution panel in Figure 1, it might be better to draw class A and class B in the upper right and lower left corners respectively. Then, adding a decision boundary (i.e., the diagonal) would be helpful.\n2. It is a little hard for me to understand what the bottom-right panel of Figure 1 is talking about before reading the experimental part.\n3. Seems that the filling color of the four panels in the bottom-right part of Figure 2 is wrong. IIUC, the color for the ablation model’s performance would be the inverse of those for the subnetwork.\n4. In section 7, the authors mentioned that ViT fails on the proposed problem, is there any possible explanation?\n5. For Figure 4, adding the legends for *** and gray dots would be helpful.", "limitations": "I believe solving the following two concerns could make the paper stronger and bring more insights to the community (it is also fine to consider them in future works).\n\n1. The paper selects the subnetwork by training a mask function $m$ and generates two subnetworks, i.e., $Sub_i$ and $M_{ablate}$, based on it. Then it might be interesting to draw the mask for different subnets (keeping the structure of the model) to see if there exist any interesting patterns. For example, it is possible that these two complementary networks are using different halves of the neurons across all layers; or they might share some lower layers but split apart in the higher layers. I guess these results might be quite helpful for us to understand HOW different subroutines are stored in different model architectures. (Maybe whether the model is pretrained also influences this split.)\n2. Besides the related works mentioned in the paper, there is also another line of works discussing how compositional mapping emerges in human language and neural network representations. It is named iterated learning, which is first proposed in the field of language evolution to explain why modern human language is so structural [1] and then extended to the deep learning conditions, e.g., emergent communication in [2] and visual question-answering in [3]. It might be interesting to consider the relationships between these works.\n\n[1] Kirby, Simon, et al. \"Cumulative cultural evolution in the laboratory: An experimental approach to the origins of structure in human language.\" PNAS 2008\n\n[2] Ren, Yi, et al. \"Compositional languages emerge in a neural iterated learning model.\" ICLR 2020\n\n[3] Vani, Ankit, et al. \"Iterated learning for emergent systematicity in VQA.\" ICLR 2021", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. Rather than the downstream generalization ability or the data attributes, the paper focuses on the composition of different rules (functions, or subroutines), which is quite novel and persuasive.\n2. The experimental designs are quite ingenious and persuasive to me, it relates the subroutines to subnetworks using the mask function on each parameter.\n3. The paper investigates different model architectures (ResNet, ViT, BERT) and different input signals (image and language).", "weaknesses": "See the limitation part.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your excellent feedback and questions about our work! We will edit the figures for clarity in the final version of the paper. We agree that a figure describing how subnetworks are distributed throughout a model would be a valuable addition to the paper, and are working on creating such a diagram for the final version. Figure 18 in the supplementary material contains this information for one model, but we agree that a better version of this figure should appear in the main text. Also, thank you for the references to the Iterated Learning literature - they are very cool and relevant! We will add a section to our Related Work describing how iterated learning can be used to encourage compositional behavior in neural networks.\n"}]

Author rebuttal:

Meta-review: I will recommend this paper for acceptance, because the reviewers were very positive about the work, stating that the approach is good and the paper is interesting (xQUi, W9E9, oWEk, DSTn), explained well (xQUi, W9E9, DSTn), and that the experiments were rich in tasks (xQUi, W9E9), and in models (xQUi). 

Rebuttal was active, informative, and cordial. New information from authors was appreciated by reviewers, and some raised their scores as a result.

Some reviews pointed out some weak points of the work, including that it was hard to know if the results are generally true, or just true of the existing models (W9E9). Other reviewers mentioned that the approach requires that one knows what to look for (W9E9). While I believe these are reasonable points to bring up, they are not unique weakpoints of this paper and the benefits of this work suggest it reaches the bar for me. 

For any future version of the work, I would make the following recommendations based on the reviewers' suggestions and my own understanding of the work: improve repo to enable reproducibility as suggested by (xQUi), better contextualization with related work (xQUi, DSTn). If possible DSTn’s limitation #1 could be considered/explored.
Decision: Accept (spotlight)