Attention-based Neural Cellular Automata
Authors: Mattie Tesfaldet
Derek Nowrouzezahrai
Christopher Pal
Venue: NeurIPS 2022 Accept (2022)
Keywords: neural cellular automata
cellular automata
vision transformer
transformer
denoising autoencoding
computer vision
deep learning

Abstract: Recent extensions of Cellular Automata (CA) have incorporated key ideas from modern deep learning, dramatically extending their capabilities and catalyzing a new family of Neural Cellular Automata (NCA) techniques. Inspired by Transformer-based architectures, our work presents a new class of _attention-based_ NCAs formed using a spatially localized—yet globally organized—self-attention scheme. We introduce an instance of this class named _Vision Transformer Cellular Automata (ViTCA)_. We present quantitative and qualitative results on denoising autoencoding across six benchmark datasets, comparing ViTCA to a U-Net, a U-Net-based CA baseline (UNetCA), and a Vision Transformer (ViT). When comparing across architectures configured to similar parameter complexity, ViTCA architectures yield superior performance across all benchmarks and for nearly every evaluation metric. We present an ablation study on various architectural configurations of ViTCA, an analysis of its effect on cell states, and an investigation on its inductive biases. Finally, we examine its learned representations via linear probes on its converged cell state hidden representations, yielding, on average, superior results when compared to our U-Net, ViT, and UNetCA baselines.

Attention-based Neural Cellular Automata
Mattie Tesfaldet McGill University, Mila
Derek Nowrouzezahrai McGill University, Mila
Christopher Pal" Polytechnique Montréal, Mila
Abstract
Recent extensions of Cellular Automata (CA) have incorporated key ideas from modern deep learning, dramatically extending their capabilities and catalyzing a new family of Neural Cellular Automata (NCA) techniques. Inspired by Transformer- bassed architectures, our work presents a new class of attention-base -based NCAs formed using spatially localized-yet globally scheme. introduce an instance this class named Vision Transformer Cellular Automata (VITCA). We present quantitative and qualitative results denoising autoencoding across six benchmark datasets, comparing ViTCA to U-Net, a U-Net-based CA baseline (UNerCA), and Vision Transformer (ViT). When com- paring across architectures configured to similar parameter complexity. VITCA architectures yield superior performance across all benchmarks and for nearly every evaluation metric. We present an ablation study on various architectural configurations of VITCA, analysis of its effect cell states, and investigation on its inductive biases. Finally, we examine its learned representations via linear probes its converged cell state hidden representations, yielding, average, superior results when compared to our U-Net, ViT, and UNetCA baselines.
seeniized-elf-attteene
Introduction
Recent developments at the intersection of two foundational ideas-Artiffiial Neural Networks (ANNs) and Cellular Automata (Cv)-have led to new approaches for constructing Neural Cel- lular Automata (NCA). These advances have integrated ideas such as variational inference [7], U-Nets [26]. and Graph Neural Networks (GNNs) [15] with promising results on prob- lems ranging from image synthesis [7, 20, 21] to Reinforcement Learning (RL) [6, 22). Trans- formers are another significant development in deep learning [41], but, until now, have not been examined under NCA setting.
Vision Transformers (ViTs) [13] have emerged competitive alternative to Convolutional Neural Network (CNN) [56] architectures for computer vision, such as Residual Networks (ResNets) [45]. ViT' leverage the self-attention
Figure 1: ViT vs. VITCA for denoising Tiny Im- ageNet [49] validation set images with 2x2 pixel masks covering 75% of the image. Top-to-bottom: noisy input, ViT, VITCA, and ground truth.
mechanisms of original Transformers [41], which have emerged the dominant approach for sequence modelling in recent years. Our work combines foundational ideas from Transformers and ViTs, leading new class of NCAs: Vision Transformer Cellular Automata (VITCA).
"Canada CIFAR Chair
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

out
out
out
(VIT)
(VIT)
out (TTCA)
coloens for
(VITCA)
visnudizing overlapping actm. inaps
local
altn
maps
colour blend
cell
heads
E
Figure 2: Global seff-organization manifested within localized self-attention. Despite operating in spatially local neighbourhoods about a cell, over time the localized (multi-head) self-attention in ViTCA experiences a global self oeff-organization admitted by its NCA nature. This circumvents the quadratic complexity of explicit global self-attention (w.rt. imput size) with linear amortization over time (recurrent CA iterations), enabling effective per-pixel dense processing. Middle: visualizing local attention maps about each cell colour-coded "splats" blended together in overlapping regions, producing a "splat map" [58]. Left, right: ViTCA iterations on a cell grid, updated from seed state converged state, given noisy input image to denoise. For each head of the cells' local attention maps, there is global agreement on the types of features to attend to (e.g., foreground contours, noise, background). Enveloping ViT by the NCA paradigm dramatically improves its output fidelity.
An effective and ubiquitous Transformer-basee learning technique for Natural Language Processing (NLP) pre-training is the unsupervised task of Masked Language Modelling (MLM), popularized by the BERT language model [34]. The success of MLMM-ased techniques has similarly inspired recent work re-examining the classical formulation of Denoising Autoencoders (DAEs) [51]. but for ViTs [3, 13, 28], introducing tasks such Masked Image Encoding [16] and Masked Feature Prediction [24] for image and video modelling, respectively. This simple yet highly-scalalle strategy of waasedd-bsedd unsupervised pre-training has yielded promising transfer learning results on vision- based downstream tasks such as object detection and segmentation, image classification, and action detection, even outperforming supervised pre- pre-training [16, 24J. We examine training methodologies for ViTCA within a DAE setting and perform extensive controlled experiments benchmarking these formulations against modern state of the art architectures, with favourable outcomes, egg., Fig.
Our contributions are as follows: first-to the best of our knowledge work is the first to extend NCA methodologies with key Transformer mechanisms. i.e., self-attention and positional encoding (and embedding), with the beneficial side-effect of circumventing the quadratic complexity of self-attention; second, our ViTCA formulation allows for lower model complexity (by limiting ViT depth) while retaining expressivity through CA iterations on a controlled state-all with the same encoder weights. This yields a demonstrably more parameter-efficht Importantly, ViTCA mitigates the problems associated with the explicit tuning of VIT depth originally needed improve performance (i.e., we use depth of 1). With ViTCA, we simply iterate until cell state convergence. Since VIT (and by extension, ViTCA) employs Layer Normalization (LN) [43] each stage of its processing, a fairly contractive model capable of fixed-point convergence guarantees [32].
[20] ViT-based model.
In relation to our first contribution, ViTCA respects CA requirements, most importantly that com- putations remain localized about a cell and its neighbourhood. As such, we modify the global self-attention mechanisms of ViT to respect this locality requirement (Fig. 2). Localized self- attention is not a new idea [4, 12, 19, 27]; however, because cells contain state information that depends on its previous state, over CA iterations the effective receptive field of ViTCA's localized self-attention grows increasingly larger until eventually incorporating information implicitly across all cells. Thus, admitting global propagation of information from spatially localized self-attention. Moreover, due to the self-organizing nature of NCAs, self-organization also manifests itself within the localized self-attention, resulting in a globally agreed-upon arrangement of local self-attention. Thus, circumventing the quadratic complexity of explicit global self-attention (w.r.t the input size)

---

neighhourlung huood
NxM N
cill update
O M1 13
cell
mask
Local ize
Z
embed
MHSA > MLP head
Fo
[1//PH] ( W/Pw
C. + C. C. C.
Figure 3: Computational overview. NCAs use stateful lattice of cells, each storing information along channels. to promote desired behaviour over the course of an evolutionary cycle. Starting from an initial seed, each cell state evolves at discrete time steps according to a homogeneous, learned update rule applied either synchronously or asynchronously (o). This update depends on the current cell state and that of its neighbours (pictured is the Moore neighbourhood [1]) In ViTCA, each cell is represented as a vector where the first C; Pw channels contain a Pи x Pw noisy input image patch (mask(x)), the next CH Pw channels contain the current output patch (z)), the following CA channels contain undefined data hidden from the loss that can be used to encode additional information (z)) ), and (optionally) the remaining Cr C.PP Pw channels contain positional information (7). The update rule (Fo) is modified ViT [13] whose self-attention mechanism is locally constrained to each cell's neighbourhood (localize).
through a linear amortization over time, and increasing the feasibility of per-pixel dense processing (as we demonstrate). This glohally consistent and complex behaviour, which arises from strictly local interactions, is a unique feature of NCAs and confers performance benefits which we observe both qualitatively and quantitatively when comparing VIT and ViTCA for denoising autoencoding.
2 Background and related work
Neural Cellular Automata. Cellular Automata are algorithmic processes motivated by the bi- ological behaviours of cellular growth and, as such, are capable of producing complex emergent (global) dynamics from the iterative application of comparatively simple (localized) rules [60]. Neu- ral Cellular Automata present more general CA formulation, where the evolving cell states are represented (typically low-dimensional) vectors and the update rule dictating their evolution is differentiable function whose parameters are learned through backpropagation from a loss, rather than handcrafted set of rules [30, 35, 59]. Neural net-based formulations of CAs in the NeurIPS community can be traced back to the early work of [59], where only small and simple models were examined. Recent formulations of NCAs have shown that when leveraging the power of deep learning techniques enabled by advances in hardware capabilities-nanee
highl-parrlleeizzale differentiable operations implemented on GPUs NCAs can be tuned to learn surprisingly complex desired behaviour, such as semantic segmentation [31] common RL. tasks such as cart-pole balancing [22]. 3D locomotion [6], and Atari game playing [6]; and image synthesis [7, 20, 21J. Although these recent formulations rely familiar compositions of convolutions and non-linear functions, it is important to highlight that NCAs are fundamentally not equivalent to "very-deep" CNNs (vs. [35]), or any other feedforward architecture (e.g., ResNets [45]), particularly, in the same way that Re- current Neural Network (RNN) is not equivalent: CNNs and other feedforward architectures induce directed acyclic computation graph (i.e., finite impulse response), whereas NCAs (and RNNs) induce a directed cyclic computation graph (i.e., an infinite impulse response), where stateful data additionally be manipulated using (learned) feedback loops and/or time-delayen controls. As such, NCAs can be viewed as a type of RNN, and both (N)CAs and RNNs are known to be Turing complete [11, 54, 57, 59..
Vision Transformers. Vision Transformers [13] are an adaptation of Transformers [41] to vision- based tasks like image classification. In contrast networks built from convolutional layers, VITs rely on self-attention mechanisms operating on tokenized inputs. Specifically, input images are divided into non-overlapping patches, then fed to Transformer after undergoing linear patch projection with an embedding matrix. While ViTs provide competitive image classification performance, the
In the of (N)CAs, Turing complete example is the Rule 110 elementary CA [1]
3

---

quadratic computational scaling of global self-attention limits their applicability in high- digh-dimensional domains, egg.. pir-pixel dense processing. Recent developments have attempted to alleviate such efficiency limitations [9, 10, 14, 17], one notable example being Perceiver I0 [5, 8] with its use of cross-attention. We refer interested readers to comprehensive survey on ViT's [18].
3 Vision Transformer Cellular Automata (ViTCA)
Building upon NCAs and ViTs, we propose new class of attention -bsedd NCAs formed using spatially localized-yet globally
sesiizzdd--eff--ttettioo scheme. We detail an instance of this class, ViTCA, by first reviewing its backbone ViT architecture before describing the "pool sampling" -based training process for the ViTCA update rule (see overview in Fig. 3).
Input tokenization. ViT starts by dividing a C. x H x xW input image X into N non-overlapping Ph x P' patches (16 x 16 in the original work [13]), followed by a linear projection of the flattened image patches with an embedding matrix E R Ldd (Fig. embed), where L = Cwr.W to produce initial tokens T E & xd, Next, handcrafted positional encoding [41] or learned positional embedding 7 E Nxd [13] is added to tokens to encode positional information and break permutation invariance. Finally, learnable class token is appended to the token sequence, resulting with T (NN+)xxd For the purposes of our task, we omit this token in all ViT-based models. In ViTCA, the input to the embedding is flattened cell grid Z N where I, CpPH Pw + Cs. Cp Cp=C, C. + Cy,, C₁ is the cell hidden size, Co is the number of output image channels (one or three for grayscale or RGB), and C. is the positional encoding size when positional encoding is (optionally) concatenated to each cell rather than added to the tokens [29].
Multi-head self-attention (MHSA). Given a sequence of tokens T, self-attention estimates the relevance of one token all others (e-g., which image patches are likely to appear together in an image) and aggregates this global information to update each token. This encodes each token in terms of global contextual information, and does so using three learned weight matrices: We E dxdd W K E Raxdd and Wv E Raddd is projected onto these weight matrices to obtain Queries Q= TWq. Q. Keys K = TWW, k, and Values V-TWv v. The self-attention layer output SA E RR is:
SA = sof tmax (OK5/Va) V.
(1)
Multi-head self-attention employs many sets weight matrices, { (WQ., WK. Wv, (Rdx(d/))) i=
o,..., (h- 1)}. The outputs of h self-attention heads are concatenated into (SAg, SA,-1) and projected onto weight matrix W E Rdxd to produce MHSA E N xxd, Self-attention explicitly models global interactions and is more flexible than grid-hased operators (e.g.. convolutions) [33, 38),
but its quadratic cost in time and memory limits its applicability to high resolution images.
Spatially localizing self-attention. The global nature of self-attention directly conflicts with the spatial locality constraint of CAs: in response, we limit the connectivity structure of the attention operation to each cell's neighbourhood. This can be accomplished by either masking each head's attention matrix (A = softmax(-..) E RVV connectivity (e.g., Fig. 3 localize), or more efficiently.
X in Eq. 1) with a banded matrix representing local
A = sof tmax A AA/VV)
s.t. (A)),) Σ (())((K))
(2)
SA A'V
(3)
new + nna) ..... 2, (i- nww - - n and 1 - (0...., (d 1)}. and with nuw (- .......,,,, 0, [ and n,, (- Here, we assume self-attention matrix A E NxN then masking it, this approach circumvents the (N)2 computation in favour of an ((NMd) alternative that indexes the necessary rows and columns during self-attention. The result is localized self-attention matrix A E ER N where M= = NH Nw < N. As we show in experiments, VITCA is still capable of global self-attention despite its localization, by leveraging stored state information across cells and their global self-organizzttion during CA iterations (Fig. 2).
with (V)z² where i= ....
(N-1)}. j= (o-
O.... [NH/2]) input flattening. Instead of explicitly computing the global
pow-left-to-bottom--ieee
Following MHSA is a multilayer perceptron (Fig. MLP) with two layers and GELU non-linearity We apply Layer Normalization (IN) [43] before MHSA and MLP, and residual connections afterwards, forming single encoding block. We use an MLP head (Fig. 3 head) to decode to a desired output.

---

with LN applied to its input, finalizing the ViTCA update rule Fg. In our experiments, ViT's head decodes directly into an image output whereas ViTCA decodes into update vectors added cells.
3.1 Update rule training procedure
To train the ViTCA update rule, we follow a "pool sampling" -based training process [7, 30] along with curriculum-based masking/noise schedule when corrupting inputs. During odd training iterations, we uniformly initialize a minibatch of cells Z (Z,, Zo) with constant values (0.5 for output channels, 0 for hidden-see Appendix A.2 for alternatives), then inject the masked input mask(X) (see Sec. 4.1). After input injection, we asynchronously update cells (a= = 50% update rate) using Fe for [8 32) recurrent iterations. We retrieve output Zo from the cell grid and apply an L1 loss against the ground truth X. We also apply overflow losses to penalize cell output values outside of [0 and cell hidden values outside of [-1,1]. We use L2 normalization on the gradient of each parameter in 8. After backpropagation, we append the updated cells and their ground truths to pool P which we then shuffle and truncate up to the first Np elements. During even training iterations, we retrieve minibatch of cells and their ground truths from P and process them as above. This encourages Fg to guide cells towards a stable fixed-point. Alg. in Appendix A details this process.
4 Experiments
Here examine VITCA through extensive experiments. We begin with experiments for denoising autocncoding, then an ablation study followed by various qualitative analyses, before concluding with linear probing experiments on the learned representations for MNIST [50], FashionMNIST [42], and CIFARIO [53]. We provide an extension to our experiments in Appendix A.
Baseline models and variants. Since we are performing pixel level reconstructions, we create a VIT baseline in which the class token has been removed. This applies identically for VITCA. Unless otherwise stated, for our ViT and ViTCA models we use a patch size of 1x1 (P== =1:w=1l 1), and only single encoding block with h= MHSA heads, embed size d = 128, and MLP size of 128. For VITCA, we choose Nи =3 and Nw (i.e., the Moore neighbourhood [.D. We also compare with a U-Net baseline similar to the original formulation [48], but based on the specific architecture from [37]. Since most of our datasets consist of 32 x 32 (resampled) images, we only have two downsampling steps opposed to five. We implement U-Net-based CA (UNetCA) baseline consisting of modified version of our U-Net with 48 initial output feature maps as opposed to 24 and with all convolutions except the first changed to 1 x respect typical NCA restrictions [7, 30].
4.1 Denoising autoencoding
We compare between our baseline models and a number of ViTCA variants in the context of denoising autoencoding. We present test set results across six benchmark datasets: a land cover classification dataset intended for representation learning (LandCoverReep) [25], MNIST, CelebA [47], FashionMNIST, CIFARIO, 10, and Tiny ImageNet (a subset of ImageNet [49]). All datasets consist of 32 x32 resampled images except Tiny ImageNet, which is at 64 x 64 resolution. During testing, we use all masking combinations, chosen in fixed order, and we update cells using a fixed number of iterations (T= 64). See Tab. 1 for quantitative results.
Briefly mentioned in Sec. 3.1, we employ masking strategy inspired by Curriculum Learning (CL) [23, 52] to ease training. This schedule follows geometric progression of difficulty tied training iterations-maxnne out at 10K training iterations. Specifically, masking starts at covering 25% of the input with 1x1 patches of noise (dropout for RGB inputs, Gaussian for grayscale), then at each shift in difficulty, new masking configurations are added to the list of available masking configurations in the following order: (2"x2" 50%), (29x20, 75%). (2) x2', 25%), (2 x2', 50%), (2 x2 75%), .... (22x 22, 75%). Masking configurations are randomly chosen from this list.
We initialize weights/parameters using He initialization [46], except for the final layer of basbd models, which are initialized to zero [30]. Unless otherwise stated, we train for I = 100K iterations, use a minibatch size b b=32, Adam W optimizer [36]. learning rate 1=100
10 3 with a cosine annealing schedule [40], pool size No = 1024, and cell hidden channel size C₁ = 32. In the case of Tiny ImageNet, b b=8 8 to accommodate training on single GPU (4SGB Quadro RTX 8000). Training typically lasts a day at most, depending on the model. Due to the recurrent iterations required per training step, CA-based models take the longest to train. To alleviate memory limitations for some of our experiments, we use gradient checkpointing [44] during CA iterations at the cost of
5

---

LandCoverRey
CelebA
MNIST
Params. #
# Params.
# Params.
PSNR f
SSIM
LPIPS +
PSNR 1
S
LPIPS
PSNR 1
SSIM
LPIPS
Baselines
U-Net
33.94
0.934
0.099
106.6K
26.23
0.906
0.075
106.6K
23.43
0.897
0.049
104.5K
ViT
30.64
0.893
0.135
83.9K
19.70
0.779
0.237
83.9K
16.02
0.631
0.254
83.4K
UNeICA
33,94
0.935
0.102
54.0K
25.66
0.882
0.091
54.0K
25.61
0.929
0.034
52.0K
VITCA
33.80
0.932
0.102
92.5K
26.53
0.913
0.066
92.5K
27.01
0.940
0.028
91.7K
ViTCA-32
34.00
0.935
0.103
92.5K
27.01
0.920
0.060
92.5K
27.68
0.946
0.026
91.7K
Variants
VyxxA-32xy
34.06
0.936
0.106
92.8K
26.75
0.898
0.072
92.8K
26.97
0.942
0.028
92.0K
ViTCA-i
33.49
0.929
0.108
54.7K
26.10
0.904
0.074
54.7K
26.03
0.930
0.033 54.3K
ViTCA-i16
33.74
0.932
0.106
54.7K
26.61
0.912
0.066
54.7K
26.42
0.935
0.031 54.3K
ViTCA-ixy
33.75
0.933
0.107
54.8K
26.51
0.894
0.076
54.8K
25.95
0.933
0.033 54.4K
VITCA-i16Xy
33,93
0.935
0.108
54.8K
26.68
0.898
0.074
54.8K
26.28
0.936
0.031 54.4K
MNSHT
CIFAR1O
Tiny ImageNet
Baselines
U-Net
24.19
0.852
0.126
104.5K
25.62
0.855
0.131 106.6K
21.93
0.775 0.203 106.6K
VIT
16.28
0.519
0.397
83,4K
20.99
0.744
0.237
83.9K
17.80
0.598
0.355 83.9K
UNeICA
23.67
0.854
0.123
52.0K
25.49
0.851
0.129
54.0K
21.78
0.773
0.204
54.0K
ViTCA
23.80
0.855
0.117
91.7K
25.61
0.856
0.127
92.5K
21.58
0.772
0.215
92.5K
ViTCA-32
24.91
0.874
0.098
91.7K
26.05
0.864
0.122
92.5K
21.94
0.781
0.202
92.5K
Variants
VITCA-32xy
24.55
0.869
0.102
92.0K
26.14
0.866
0.120
92.8K
22.03
0.783
0.199
92.8K
ViTCA-i
22.84
0.827
0.139
54.3K
25.42
0.853
0.132
54.7K
21.75
0.776
0.211
54.7K
ViTCA-i16
23.32
0.839
0.127
54.3K
25.65
0.856
0.128
54.7K
21.72
0.774
0.213
54.7K
ViTCA-ixy
23.54
0.848
0.123
54.4K
25.85
0.861
0.125
54.8K
21.95
0.782
0.201
54.8K
ViTCA-i16xy
23.59
0.848
0.121
54.4K
25.98
0.863
0.123
54.8K
21.99
0.782
0.201
54.8K
Table Comparing denoising autoencoding results between baselines and ViTCA variants. ViTCA variants include: 32 (32 heads). 16 (16 heads), i (inverted bottleneck), xy (xy-coordinate positional encoding). Boldface and underlined values denote the best and second best results. Metrics include Peak Signal-to- Noise Ratio (PSNR; dB), Structural Similarity Index Measure (SSIM; values in [0, 1) [55], Learned Perceptual Image Patch Similarity (LPIPS; values in [0, 1) [39].
backpropagation duration and slight variations in gradients due its effect on round-off propagation. We also experiment with a cell fusion and mitosis scheme as an alternative. See Appendix A for details on runtime performance, gradient checkpointing, and fusion and mitosis.
Amongst baselines, ViTCA outperforms on most metrics across the majority of datasets used (10 out of 18). Exceptions include I. LandCoverRep, where UNetCA universally outperforms by small margin, likely due to the texture-dominant imagery being amenable to convolutions. Notably, ViTCA strongly outperforms on MNIST. Although MNIST is a trivial dataset for common tasks such classification, our masking/noise strategy turns it into a challenging dataset for denoising autoencoding, e.g., it is difficult for even a human to classify 32 x 32 MNIST digit 75% corrupted by 4 4 patches of Gaussian noise. We hypothesize that when compared to convolutional models, ViTCA's weaker inductive biases (owed to attention [5, 81) immediately outperform these models when there are large regions lacking useful features, e.g., MNIST digits cover a small space in the canvas. This is not the case with MNSST, where the content more filled out. Between baselines and ViTCA variants, ViTCA-32 (32 heads) and 32xy (xy-coordinate positional encoding) outperform all models by large margins, demonstrating the benefits of multi-head self-attention. We also experiment with a parameter-reduced (by 60%), inverted bottleneck variant where d d= 64 and MLP size is 256, often with a minimal reduction in performance.
4.1.1 Ablation study
In Tab. 2 perform ablation study using the baseline VITCA model above reference on CelebA. Results are ordered in row-wise blocks, top-to-bottom. Specifically, we examine the impact of varying the cell hidden size Ck; the embed size d; the number of MHSA heads h; the depth (# encoders), comparing both ViTCA (used throughout the table) with ViT; and in the last block we examine the impact of various methods of incorporating positional information into the model.

---

Specifically, we examine the use of: (1) xy yyccordinate-basee positional encoding
PSNR
SSIM
LPIPS
# Params.
25.61
0.898
0.086
86.3K
concatenated ("injected") to cells, and; 16
26.11
0.909
0.070
88. 48.4K
(2) a Transformer-based positional encod-
32
26.53
0.913
0.066
92.5K
ing (or embedding, if learned) added into 64
26.53
0.913
0.066
100.7K
embed. These two categories are subdi- 128
26.51
0.912
0.066
117.2K
vided into: (la) crafted Fourier features [29] with four dou- blings of base frequency, i.e., 7= (sin 2 xp, cos тр. sin 2d xp, cos 20 Tp) E
of hand-
256
26.77
0.915
0.063
150,
512
26.78
0.916
0.063
215.9K
8*
21.67
0.814
0.258
2.0K
Embed dim
16
23.22
0.853
0.183
4.5K
IN Pw) where 5 and is the pixel coordinate (normalized to [-1,1]) for each pixel the cell is situated on (one pixel since PH
32
24.94
0.875
0.110
10.9K
64
25.69
0.898
0.084
29.9K
128*
26.05
0.904
0.075
92.5K
Pw= ===1; 1); (Ib)
of both
256'
26.36
0.911
0.067
316.0K
Fourier features and explicit xy xy-coordinates concatenated; (Ic) xy-only xy-coordinates; (2a) handcrafted (our baseline approach)- sinusoidal encoding 7 Nxd similar to (la)
512*
19.93
0.768
0.274
1.2M
25.01
0.890
0.096
76.0K
26.53
0.913
0.066
92.5K
Heads
26.77
0,916
0.062
92.5K
but following a Transformer-base
approach
16
26.78
0.917
0.062
92.5K
[41], and: (2b) learned- Icarned embedding Y
32
27.01
0.920
0.060
92.5K
E ER xd following the original ViT approach [13]. To further test the ouff-organzzig capabil-
64
26.94
0.919
0.061
92.5K
VITCA-1
26.53
0.913
0.066
92.5K
ities of VITCA, we also include: (3) none no explicit positioning provided, where we let the cells localize themselves.
ViTCA-2'
10.82
0.225
0.771
175.3K
Depth
ViTCA-3*
9.70
0.165
0.793
258.0K
VIT-1
19.70
0.779
0.237
83.9K
As shown in Tab. 2, ViTCA benefits from increase to most CA and Transformer-centric parameters, the cost of computational com- plexity and/or an increase in parameter count. noticeable decrease in performance is ob- served when embed size d= 512, most likely due to the vast increase in parameter count ne- cessitating more training. In the original ViT, multiple encoding blocks were needed before the model could exhibit performance equiva- lent their baseline CNN [13], as verified in our ablation with our VIT. However, for ViTCA we notice an inverse relationship of the effect of Transformer depth, causing divergence in cell state. is not clear why this is the case, as we have observed that the LN layers and over- flow losses otherwise encourage contractive Fg. This is investigation
VIT-21
25.20
0.900
0.074
166.7K
VIT-31
26.10
0.914
0.065
249.4K
sincos5
26.92
0.917
0.062
95.1K
type
sincos5xy
27.00
0.919
0.059
95.3K
xy
26.45
0.894
0.077
92.8K
handcrafted
26.53
0.913
0.066
92.5K
learned
26.16
0.910
0.071
223.6K
26.28
0.890
0.081
92.5K
Table Quantitative ablation for denoising autoen- coding with VITCA (unless otherwise stated via pre- fix) on CelebA [47]. Boldface and underlining de- note best and second best results. Italicized items de- note baseline configuration settings. "Trained with gradient checkpointing [44], which slightly alters round-off error during backpropagation. resulting in slight variations of results compared to training without checkpointing. See Appendix A.2.
leave for future work. Despite the benefits of increasing h. we h = for our baseline optimize runtime performance. Finally, show that VITCA does dramatically suffer when no explicit positioning is used-in contrast to typical Transformer- bbaseed models cells are still able to localize themselves by relying their stored hidden information.
4.1.2 Cell state analysis
Here provide empirically- based qualitative analysis the effects VITCA and UNetCA have on cell states through several experiments with our pre-trained models (Fig. 4 (a,b,c)). We notice that in general, ViTCA indefinitely maintains cell state stability while UNetCA typically induces divergence past a certain point. An extended analysis is available in Appendix A.3.
Damage resilience. Shown in Fig. (a), we damage a random H W/2 patch of cells with random values ~ twice in succession. ViTCA is able to maintain cell stability despite not being trained to deal with such noise, while UNetCA induces divergence. Note both models are simultaneously performing the typical denoising task. We also note that ViTCA's inherent damage resilience is in contrast to recent NCA formulations that required explicit training for [7, 30].
7

---

255
200
9
1000
G
63
(d)
(e)
97
738
(8)
(4)
(c)
224
464
201
9-1
118t
Figure 4: Qualitative results. Gold boxes are inputs, green ground truths, purple ViTCA outputs, and blue UNetCA outputs. We analyze the effects of ViTCA and UNeTCA on cell states in terms of: (a) damage resilience; (b) convergence stabilility, and; (c) hidden state PCA visualizations of converged cell grids for all examples in FashionMNIST [42]. We also investigate update rule inductive biases in terms of adapting to: (f) varying inputs during cell updates; (d) varying cell update rates: (e) noise configurations unseen during training;
(g) unmasked and completely masked inputs, and; (h) spatial interpolation enabled by our various methods of incorporating cell positioning.
Convergence stability. Fig. 4 (b) shows denoising results after 2784 cell grid updates. VITCA is able to maintain stable cell grid state while UNetCA causes cells to diverge.
Hidden state visualizations. Fig. 4 (c) shows 2D and 3D PCA dimensionality reductions on the hidden states of converged cell grids for all examples in FashionMNIST [42]. The clusters suggest some linear separability the learned representation, motivating our probing experiments in Sec. 4.2.
4.1.3 Investigating update rule inductive biases
Here we investigate the inductive biases inherent in ViTCA and UNetCA by testing their adaptation to various environmental changes (Fig. 4 (d.e.f.g.h)).
A daptation to varying update rates. Despite being trained with a o= 50% cell update rate, VITCA is able to adapt to varying rates (Fig. 4 (d)). Higher rates result in a proportionally faster rate of cell state convergence, and equivalently with lower rates. UNetCA exhibits a similar relationship, although is unstable at a = 100% (see Appendix A.3). For details comparing training with synchronous vs. asynchronous cell grid update, see Appendix A.2.
Generalization to noise unseen during training, VITCA is capable of denoising configurations of noise it has not been trained on. Fig. 4 (e; left-to-right): 4x 1 and 1 X 4 patches of Gaussian noise at 65% coverage. In contrast, UNetCA induces a cell state divergence (see Appendix A.3).
Adaptation to changing inputs. At various moments during cell updates, re-inject cells with new masked inputs (Fig. 4 (f)). ViTCA is able to consistently adapt cells to new inputs while UNeCCA experiences difficulty past certain point (e.g., ., at 464 iterations in the figure).
Effects of not vs. completely masking input. Fig. 4 (g: left): VITCA able to perform autoencoding despite not being trained for it. UNetCA induces cell grid divergence (see Appendix A.3). Fig. (g: right): Interestingly, when the input is completely masked, ViTCA outputs the median image [37]. UNeICA does not exhibit such behaviour and instead causes cells to diverge (see Appendix A.3).
Spatial interpolation. We use ViTCA models trained 32 32 using various types of positioning to generate 128 x 128 outputs during inference, assuming an identical cell grid resolution. Fig. 4 (h; top-to-bottom of outputs): xy-coordinates, no positioning, Fourier features [29], Fourier features concatenated with xy-coordinates, and Transformer based handcrafted positional encoding (baseline) [41]. Results are ordered from best to worst. The baseline approach not capable of spatial interpolation due to being 1D positioning, while, as expected, the 2D encodings make it capable. Surprisingly, removing Fourier features and using only xy-coordinates results higher fidelity interpolation. We believe this to be caused by the distracting amount of positional information

---

MNIST
FashionMNIST
CIFAR1O
Ace. 1
Params.
Acc. f
Params.
Acc. 1
Params.
Baselines
U-Net
96.3
15.4K
86.2
15.4K
52.3
13,4K
ViT
92.1
1.3M
83.4
1.3M
34.5
1.3M
UNeCCA
96.3
327.7K
89.5
327.7K
55.1
327.7K
VITCA
96.7
327.7K
89.7
327.7K
50.2
327.7K
ViTCA-32
96.3
327.7K
89.8
327.7K
55.1
327.7K
Variants
VITCA-32Xy
96.3
327.7K
89.5
327.7K
53.6
327.7K
ViTCA-i
95.8
327.7K
89.6
327.7K
49.4
327.7K
VITCA-i16
95.7
327.7K
90.1
327.7K
50.7
327.7K
ViTCA-ixy
96.2
327.7K
89.6
327.7K
50.2
327.7K
VITCA-i16xy
96.5
327.7K
89.6
327.7K
52.7
327.7K
Linear classifier
93.0
10.3K
84.7
10.3K
39.0
30.7K
2-layer MLP, 100 hidden units
98.2
103.5K
89.4
103.5K
46.0
308.3K
2-layer MLP, 1000 hidden units
98.5
1.0M
89.6
1.0M
49.7
3.1M
Table 3: Linear probe [28] test accuracies (%) of baseline and variant models. Model variants are labelled as in Tab. 1. All baselines and variants pre-trained for denoising autoencoding and kept fixed during probing. A linear classifier and 2-layer Multilayer Perceptrons (MIP) were trained on raw image inputs. Parameter counts exclude fixed parameters. Boldface and underlined values denote the best and second best results, respectively. Interestingly, CA-based models trained for denoising autoencoding on increasingly challenging datasets produce an increasingly more useful self-supervised representation for image classification compared to non-CA-based models.
Fourier features provide to cells, as cells can instead rely on their hidden states to store higher frequency positional information. Finally, with no explicit positioning, VITCA is still able to perform high-quality interpolation even exceeding using Fourier features-by taking advantage of its self- organizing nature. As a side note, we point attention to the fact that ViTCA is simultaneously denoising at a scale space it has not been trained on, exemplifying its generalization capabilities.
4.2 Investigating hidden representations via linear probes
Here we examine the learned representations of our models pre-trained for denoising. We freeze model parameters and learn linear classifiers on each of their learned representations: converged cell hidden states for CA-based models, bottleneck features for U-Net, and LN'd tokens for ViT. This is common approach used probe learned representations [28]. Classification results MNIST, FashionMNiST, and CIFARIÓ are shown in Tab. 3 and we use the same training setup as for denoising, but without any noise. For comparison, and two 2-layer MIPPs of varying complexity, all trained directly on raw pixel values. Correlations between denoising performance in Tab. 1 and classification performance in Tab. can be observed. Linear classification accuracy on ViTCA-basee using other model-based features or raw pixel values, even outperforming the MLPs most cases.
also provide results using a linear classifier
features typically exceeds classification accuracy
Discussion
We have performed extensive quantitative and qualitative evaluations of our newly proposed ViTCA on variety of datasets under a denoising autoencoding framework. We have demonstrated the superior denoising performance and robustness of our model when compared a U-Net-based CA baseline (UNetCA) and ViT, as well as its generalization capabilities under a variety of environmental changes such as larger inputs (i.e., spatial interpolation) and changing inputs during cell updates.
Despite the computation savings-owed to our circumvention of self-attention's quadratic complexity by spatially localizing it within ViTCA-there remains the same memory limitations inherent to all recurrent models: multiple recurrent iterations are required for each training iteration, resulting in larger memory usage than feedforward approach. This limits single-GPU training accessibility. We have experimented with gradient checkpointing [44] but found its trade-off for increased back- propagation duration (and slightly different gradients) less than ideal. To fully realize the potential of NCAs nelf-organizztionn inherent distributivity, etc.), we encourage follow-up work to address this limitation. Adapting recent techniques using implicit differenniation is one avenue to circumvent these issues [2, 32). Also, as mentioned in our ablation (Sec. 4.1.1), we hope to further investigate the instabilities caused by increasing the depth of ViTCA.

---

Acknowledgments and disclosure of funding
First and foremost, M.T. thanks their former supervisor and mentor, Konstantinos (Kosta) G. Derpanis, for his invaluable support throughout the project. M.T. also thanks Martin Weiss for his helpful feedback on implementing the linear probe experiments (Sec. 4.2); Olexa Bilaniuk for his assistance in investigating the gradient differences caused by Py PyTorch's s gradient checkpointing implementation (see Appendix A.2), and; the Mila Innovation, Development, and Technology (IDT) team for their overall technical support, particularly, their tireless efforts maintaining cluster reliability during the crucial moments preceding the submission deadline. The authors acknowledge the material support of NVIDIA in the form of computational resourees.
M.T. is partially supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) Canada Graduate Scholarship Doctoral [application number (GSDD-551928-222 and C.P. are each partially supported by a NSERC Discovery Grant [application IDs 5011 1360 and 5018358, respectivelyl. D.N. thanks Samsung Electronics Co. Ltd. for their support. C.P. thanks CIFAR for their support under the Al Chairs Program.
D.N.
References
[1] E. W. Weisstein, Moore neighborhood. From MathWorld-A Wolfram Web Resource. [Online]. Available: https: htt//w/ttwwwoddooooom wolfram.. com/Moor wowooeeeighoorbreeeeeeeooooeeeee html.
[2] S. Bai, Z. Geng. Savani, and J. Z. Kolter, "Deep equilibrium optical flow estimation," in IEEF/CVF Computer Vision and Puttern Recognition Conference (CVPR), 2022.
[3] H. Bao, L. Dong, S. Piao, and F. Wei, "BEiT: BERT pre-training of image transformers," in International Conference on Learning Representations (ICLR), 2022. [Online]. Available: https:// hatps:///pperree /pwpreeepeeeeeeeeeeeeeeeeeeeeeee
[4] C.-F. Chen, R. Panda, and Q. Fan, "Region ViT: Regional-to-local attention for vision trans- formers," in International Conference on Machine Learning (ICML), 2022. [Online]. Available: net. forum?id=r_... V
[5] A. Jaegle et al., "Perceiver 10: A general architecture for structured inputs & outputs," in International Conference on Learning Representations (ICLR), 2022.
[6] E. Najarro, S. Sudhakaran, C. Glanois, and S. Risi, "HyperNCA: Growing developmental net- works with neural cellular automata," in International Conference on Learning Representations Workshops (ICLR Workshops), 2022.
[7] B. Palm, M. G. Duque, Sudhakaran, and Risi, "Variational neural cellular automata," in International Conference Learning Representations (ICLR), 2022. [Online], Available: www. (adrrunmddd7/EFAAcMBB.....
https://openreeet
[8] W. Yifan, C. Doersch, R. Arandjelović, J. Carreira, and A. Zisserman, "Input-level induc- tive biases for 3d reconstruction," in IEEE/CVF Computer Vision and Pattern Recognition Conference (CVPR), 2022.
[9] A. Ali et al., "XCIT: Cross-covariance image transformers," in Neural Information Processing Systems (NeurIPS), 2021.
[10] A. Arnab, M. Dehghani, G. Heigold, C. Sun, M. Lučić, and C. Schmid, "ViVIT: A video vision transformer," in IEEE/CVF International Conference Computer Vision (ICCV), 2021, pp. 6836-6846.
[11] P. Christen and O. Del Fabbro, "Automatic programming of cellular automata and artificial neural networks guided by philosophy," in New Trends in Business Information Systems and Technology, 2021, pp. 131-146.
[12] X. Chu et al., "Twins: Revisiting spatial attention design in vision transformers," in Neural Information Processing Systems (NeurIPS), 2021.
[13] A. Dosovitskiy et al., "An image is worth 16x16 words: Transformers for image recognition at scale," International Conference on Learning Representations (ICLR), 2021.
[14] Fan et al., "Multiscale vision transformers,"
IEEE/CVE International Conference on Computer Vision (ICCV), 2021, pp. 6824-6835.
[15] D. Grattarola, L. Livi, and C. Alippi, "Learning graph cellular automata," in Neural Information Processing Systems (NeurIPS), 2021, pp. 20 - 994.
10

---

[16] K. He, X. Chen, S. Xie. Li, P. Dollár, and R. Girshick, "Masked autoencoders are scalable vision learners," arXiv preprint arXiv:211..06377, 2021.
[17] D. A. Hudson and L. Zitnick, "Generative adversarial transformers," in International Confer-
ence on Machine Learning (ICML), 2021, pp. 1487-4499
[18] S. Khan, M. Naseer, M. Hayat, S. W. Zamir, F. S. Khan, and M. Shah, "Transformers in vision:
A survey," ACM Computing Surveys (CSUR), 2021.
[19] Z. Liu et al., "Swin transformer: Hierarchical vision transformer using shifted windows," in IEEE/CVF International Conference on Computer Vision (ICCV), 2021, pp. 10012-10022.
[20] A. Mordvintsev and E. Niklasson, "HNCA: Texture generation with ultra-compact neural cellular automata," arXiv preprint arXiv:2111.1354. 2021.
[21] E. Niklasson, A. Mordvintsev, E. Randazzo, and M. Levin, "Self- organiinggn textures." Distill, (tarrg//22////ee 2w2////ettteeee..///
2021, https: //di::/ddsstillll wewttilllubbuaaeeeeeeeeeeeeeeeee
[22] A. Variengien, S. Nichele, T. Glover, and S. Pontes-Filho, "Towards self-organized control: Using neural cellular automata to robustly control a cart-pole agent," " in Innovations in Machine Intelligence (IMI), 2021, pp. 1-14.
[23] X. Wang. Y. Chen, and W. Zhu, "A survey on curriculum learning." IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2021.
[24] C. Wei, H. Fan, S. Xie, C.-Y. Wu, A. Yuille, and C. Feichtenhofer, "Masked feature prediction for self-supervised visual pre-training," arXiv preprint 1rXiv:21/2.00/33, 2021.
[25] C. Yeh et al., "SustainBench: Benchmarks for monitoring the sustainable development goals with machine learning." in Neural Information Processing Systems (NeurIPS), 2021.
[26] D. Zhang, C. Choi, Kim, and M. Kim, "Learning generate 3D shapes with generative cellular automata." in International Conference on Learning Representations (ICLR), 2021. [27] P. Zhang et al., "Multi-scale vision longformer: A new vision transformer for high-resolution image encoding," in JEEE/CVF International Conference on Computer Vision (ICCV), 2021, pp.
[28) M. Chen et al., "Generative pretraining from pixels," in International Conference on Learning Representations (ICLR), 2020, pp. 1691-1703.
[29] B. Mildenhall, P. P. Srinivasan, M. Tancik, J. T. Barron, R. Ramamoorthi, and R. Ng, "NeRF: Representing scenes as neural radiance fields for view synthesis," European Conference on Computer Vision (ECCV), 2020, pp. 405-421.
[30] A. Mordvintsev, E. Randazzo, E. Niklasson, and M. Levin, "Growing neural cellular automata," Distill, 2020, https:
pub. pubb22222 2020/ growing-ca.
[31] M. Sandler, A. Zhmoginov, L. Luo, A. Mordvintsev, E. Randazzo, et al., "Image segmentation via cellular automata," arXiv preprint ar 200i:22008.00 04966, 2020.
[32] S. Bai, J. Z. Kolter, and V. Koltun, "Deep equilibrium models," Neural Information Processing Systems (NeurIPS), 2019.
[33] J.-B. Cordonnier, A. Loukas, and M. Jaggi, "On the relationship between self-attention and convolutional layers," 2019.
[34] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, "BERT: Pre-training of deep bidirectional transformers for language understanding.." " in Proceedings of the North American Chapter of the Association for Computational Linguistics (NAACL): Human Language Technologies,
2019, pp. 4171-4186.
[35] W. Gilpin, "Cellular automata as convolutional neural networks," " Physical Review E (PRE), vol. 100, p. 032 402, 3 2019.
[36] I. Loshchilov and F. Hutter, "Decoupled weight decay regularization," " in International Confer- ence on Learning Representations (ICLR), 2019.
[37] J. Lehtinen et al., "Noise2noise: Learning image restoration without clean data," in Interna- tional Conference on Machine Learning (ICML), 2018, pp. 2965-2974.
[38] J. Pérez, J. Marinković, and P. Barceló, "On the turing completeness of modern neural network architectures," in International Conference on Learning Representations (ICLR). 2018 [39] R. Zhang, P. Isola, A. A. Efros, Shechtman, and O. Wang. "The unreasonable effectiveness of deep features as a perceptual metric," in IEEF/CVF Computer Vision and Pattern Recognition Conference (CVPR), 2018, pp. 586-595.

---

[40] I. Loshchilov and F. Hutter, "SGDR: Stochastic gradient descent with warm restarts," Interna- tional Conference on Learning Representations (ICLR), 2017.
[41] A. Vaswani et al., "Attention is all you need," in Neural Information Processing Systems (NeurIPS), 2017.
[42] H. Xiao, K. Rasul, and R. Vollgraf, "Fashion-MNIST: A novel image dataset for benchmarking machine learning algorithms," arXiv preprint arXiv:1708.07744 2017.
[43] I. Ba, R. Kiros, and G. E. Hinton, "Layer normalization," arXiv preprint arXiv: 2016.
[44] T. Chen, B. Xu, C. Zhang, and C. Guestrin, "Training deep nets with sublinear memory cost," arXiv preprint
2016.
[45] K. He, X. Zhang, S. Ren, and Sun, "Deep residual learning for image recognition," " in IEEE/CVF Computer Vision and Pattern Recognition Conference (CVPR), IEEE, 2016, pp. 770-778.
[46] K. He, X. Zhang, S. Ren, and J. Sun, "Delving deep into rectifiers: Surpassing human-level performance on imagenet classification," in IEEE/CVF International Conference on Computer Vision (ICCV), 2015, pp. 1026-1034.
[47] Z. Liu, Luo, X. Wang, and X. Tang, "Deep learning face attributes in the wild," in IEEE/CVF International Conference on Computer Vision (ICCV), 2015, pp. 3730-3738.
[48] O. Ronneberger, P. Fischer, and T. Brox, "U-Net: Convolutional networks for biomedical image segmentation." in International Conference on Medical Image Computing and Computer- Assisted Intervention (MICCAI), Springer, 2015, pp. 234 144-241.
[49] O. Russakovsky et al., "ImageNet Large Scale Visual Recognition Challenge," International Journal of Computer Vision (IJCV), pp. 211-252, 2015.
[50] L. Deng, "The MNIST database of handwritten digit images for machine learning research," IEEE Signal Processing Magazine, pp. 141-142, 2012.
[51] P. Vincent, H. Larochelle, I. Lajoie, Y. Bengio, P.-A. Manzagol, and L. Bottou, "Stacked denoising autoencoders: Learning useful representations in deep network with a local denoising criterion.." Journal of Machine Learning Research (JMLR), 2010.
[52] Y. Bengio, J. Louradour, R. Collobert, and J. Weston, "Curriculum learning." in International Conference on Machine Learning (ICML), 2009, pp. 41-48.
[53] A. Krizhevsky, G. Hinton, al., Learning multiple layers of features from tiny images, //wp:///ww.cc cs. toronto.........o...... wwt/""rri/leerriiiaa
features- 2009 TR. pdf, 2009.
[54] M. Cook, "Universality in elementary cellular automata," Complex systems, pp. 1-40, 2004.
[55] Z. Wang, A. C. Bovik, R. Sheikh, and E. Simoncelli, "Image quality assessment: From error visibility to structural similarity," in IEEE Transactions on Image Processing (TIP), 2004, pp. 600-612.
[56] Y. LeCun, I.. Bottou, Y. Bengio, and P. Haffner, "Gradient-based learning applied to document recognition," " Proceedings of the IEEE, pp. 2278-2324, 1998.
[57] H. T. Siegelmann and E. D. Sontag, "On the computational power of neural nets," Journal of Computer and System Sciences (JCSS), pp. 132-150. 1995.
[58] R. A. Crawfis and N. Max, "Texture splats for 3D scalar and vector field visualization," in IEEE Conference on Visualization, 1993, pp. 261-266.
[59] N. H. Wulff and J. A. Hertz, "Learning cellular automaton dynamics with neural networks," in Neural Information Processing Systems (NeurIPS), 1992. pp. 631-638.
[60] J. V. Neumann and A. W. Burks, Theory of Self Self- Self-Reproducing Automata. USA: University of Illinois Press, 1966.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Sec. 5.
12

---

(c) Did you discuss any potential negative societal impacts of your work? [No] Although we feel our work demonstrates the potential of NCAs as viable alternatives common recurrent network architectures (ViTCA being our evidential contribution), our exper- iments intentionally tend towards the direction of optimizing model efficiency (and single- UUU training accessibility) rather than towards the increasingly popular direction of scaling upwards. However, as much as our work demonstrates the downward-scalinn capabilities of NCAs, we also acknowledge that this similarly applies going upward, and as such, can be abused (e.g., creating a seeefakee-capallee ViTCA).
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yss]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results [N/A]
(b) Did you include complete proof's of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or URL)? [Yes] Code and instructions to reproduce results are included in the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running ex- periments multiple times)? [No] Given the combination of time and computational restrictions and our exhaustive list of experiments, we opted to prioritize experiment variety and dataset coverage different random seeds. For all experiments, we kept a fixed random seed, even point- ing out (deterministic) differences caused by gradient checkpointing when used (see Appendix A).
implicit substitute for re-running experiments under
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]]
(b) Did you mention the license of the assets? [N/A] Licensed frameworks used such as
PyTorch (BSI--style) and Hydra (MIT) will be mentioned in acknowledgements.
(c) Did you include any new assets either in the supplemental material or URL?
[No] No new assets-ast aside from code and training our models were created for the purposes of this work.
(d) Did you discuss whether and how consent obtained from people whose data you's 're using/curating? [No] We used publicly available datasets.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] Although not discussed in the manuscript, we would like to point that the datasets we used that could potentially contain personally identifialle information (CelebA, CIFARIO, Tiny ImageNet) each have restrictions and/or acknowledd sekkowleegeeentss of such potential issues. Also, our work is not focused on classifying persons and ViTCA is not a generative model, e.g., it can not generate new faces.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "xn1NWE-ONQ", "reviewer": "Reviewer_mu6v", "summary": "The paper presents a neural cellular automata (NCA) architecture for image denoising that replaces the typical convolutional layers with a vision transformer.\n\nThe experiments show that the proposed architecture achieves marginally better results compared to two baselines on three simple datasets, and the authors show that their model appears to be stable after converging to a target image (NCAs are known to be unstable when evaluated on longer horizons than the one seen at training time).", "questions": "Overall, I lean towards a borderline reject which can turn into a borderline accept if the following questions are addressed.\n\n1. What is the meaning of \"it is a fairly contractive model capable of fixed-point convergence guarantees\"?\n\n2. The attention operation in Equations (1) and (3) is at the patch level, not at the cell level. This means that ViTCA is not comparable 1-to-1 with pixel-level NCAs unless the patch size is set to 1x1. \nAlso, it might confuse the reader to refer to the \"Moore neighborhood\" in line 177 when talking about the patch size, because this term is typically used in CA literature to indicate the neighborhood of a cell (as it is used to compute the update). Here, the effective neighborhood of the cell is 9x9.\nDid I misunderstand something?\n\n3. I couldn't find how the positional encodings are computed. IF PEs provide unique coordinates for each pixel, doesn't that defeat the principle of locality of CAs?\n\n4. Why is the ViTCA baseline configured to have a patch size of 1x1, while all the other ViTCA models have 3x3?\n\n5. The number of parameters in Tables 1, 2, and 3 appears to be misreported. \nA few examples: \n    - Table 1, no difference between ViTCA (4 heads) and ViTCA-32 (32 heads)\n    - Table 2, no difference between ViTCA with 4-64 heads\n    - Table 3, no difference between the variants\n    - Table 3, no difference between MLPs with 100 or 1000 hidden units on CIFAR10\n\n    The absence of differences in Tables 1 and 2 is especially puzzling and important to clarify, because ViTCA-32 is the only model that can consistently surpass the baselines (while, e.g., ViTCA-4 cannot).\n\n6. Why use an overflow loss instead of an activation function (sigmoid, tanh) that forces the updates to be in the required ranges?\n\n7. Figure 3 shows some noise sampled from a uniform distribution being injected in the cell update. Where is this described in the text?\n\n8. Since all NCAs are image-to-image maps, why didn't the authors consider other NCA baselines like the original NCA [30] or the Variational NCA [7]? Why not consider other recurrent baselines too? As it is (and considering point 5 above), the comparisons are not very informative.\n\nI'm looking forward to the discussion with the authors. ", "limitations": "The limitations are not discussed extensively besides what concerns memory costs. \nI have pointed out a few issues in my questions that could be discussed better (e.g., point 3). \n\nThere are no societal concerns with the work.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The idea of the paper is novel, although it doesn't provide substantial contributions besides replacing convolutions with transformers.\nThe quality of the paper is good, the experiments go fairly in-depth although on just one task of image denoising (which is less interesting than texture generation or other forms of morphogenesis, in the reviewer's personal opinion).\n\nThe clarity of the paper is good, almost all details are reported clearly and there are only a few details that require clarification (see below).\nThe significance of the paper is modest, since it is not even clear that the proposed method provides real advantages compared to the two simple baselines tested by the authors. The paper is unlikely to have an impact on the NCA community, and surely not on the much larger computer vision community. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "q8Tq-QfIXhG", "reviewer": "Reviewer_GAh5", "summary": "This paper proposes a novel combination of vision transformers and Neural Cellular Automata (NCAs), and uses them to create denoising autoencoders. An NCA is essentially a cellular automata with the node updates being performed by a neural net. The ViTCA proposed here adds to this attention heads that are only focused on neighboring cells, and includes positional encodings. The paper demonstrates superior performance to a ViT on denoising autoencoder tasks, and demonstrates the robustness of the model to various perturbations.\n\nI have read the authors' responses and am happy to update my rating to a 7. Their responses were quite thorough, although (correct me if I'm wrong) they didn't respond to the \"one task\" critique.\n\n\n", "questions": "1. What are the essential differences between your model and a universal transformer with local attention? Universal transformers simply use the same weights over and over, so they are recurrent (Dehghani, et al. 2018). One difference is the asynchronous update rule. Others?\n\n2. On lines 209-210, you mention that ViTCA outperforms the other baselines on 10 out of the 18 datasets, although you are reporting only 6. Are there 12 more datasets you aren’t telling us about??\n\n3. Instead of overflow loss, have you tried just using nonlinear activation functions that stay within the desired range?\n\nMostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, Łukasz Kaiser (2018) Universal Transformers. arXiv:1807.03819.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. This is a novel combination of transformers and neural cellular automata.\n\n2. The results look very good compared to a vanilla ViT. E.g., Figure 1 and parts of Figure 2 make a good case for the model.\n\n3. While the baseline ViT used for comparison has slightly fewer parameters than the baseline ViTCA, making for an unfair comparison, smaller versions of the ViTCA (e.g., ViTCA-i) also outperform it with many fewer parameters. This could be better emphasized in the paper. Although this does beg the question - how would an inverted bottleneck ViT with a similar number of parameters perform on this task?\n\n4. The writing is fairly clear, although Figures 2 and 3 are not.\n\n5. I believe, given the results, that this work is significant, but they only demonstrated efficacy on one task, which reduces enthusiasm somewhat.\n\n\nWeaknesses:\n\n1. It is very hard to understand what is going on in Figures 2 and 3. I can make some sense of Figure 3, but Figure 2 is a mystery. I don’t know what a “splat map” is, and I can’t tell that the cells are focusing on foreground, noise and background, as mentioned in the caption. The authors should try showing these figures to a colleague and finding out what they have to explain to get the idea across, and then simplify the figure to make this clear.\n\n2. This reviewer, at least, would have appreciated a demonstration of this architecture on another problem (e.g., semantic segmentation), rather than a deep dive into the model robustness to ablations and various perturbations (section 4.1.1-4.1.3), which could have been relegated to the supplementary material. \n\n3. This model is similar to a universal transformer, which also uses essentially depth 1 (since the parameters are used over and over), with iterative processing.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "itN2a3nTANu", "reviewer": "Reviewer_EYVF", "summary": "This paper proposes a new family of Neural Cellular Automata (NCA) based on visual Transformer for the first time. The main difference from the plain ViT is the use of a specially localized self-attention mechanism that is still globally organized, thus yielding a parameter-efficient model.  Quantitative and qualitative experiments show that the proposed ViTCA outperforms U-Net, UNetCA, and ViT on various benchmarks. The learned representations are also verified via linear probes evaluation.", "questions": "- Choosing ViT as a baseline to show the superiority of the proposed ViTCA makes sense. But why do you adopt U-Net, the CNN architecture, as the baseline? And why the proposed ViTCA succeeds while U-net fails? The authors do not describe the motivation and the reasons for such an experimental setup. \n- Linear probes have been popular evaluation protocols to show the learning representation via self-supervised learning. I am wondering how does the proposed model perform using fine-tuning? Can the authors provide fine-tuning results or explain the reason why it is not good if fine-tuning performs poorly?\n- The proposed model requires iterative training to converge. How can you ensure the stability of the proposed model?\n- Performing experiments on MNIST and CIFAR 10 datasets is OK. It is better to validate the performance on larger datasets to show the practicality of the proposed model. The authors can either provide some analysis if the performance is not good.", "limitations": "The authors have discussed the limitations in Sec 5.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ This paper provides a new perspective on neural cellular automata with a visual Transformer architecture. Although it is a combination of problem and architecture, the authors propose an effective self-attention scheme to improve the model.\n+ The experiments are relatively complete and can verify the proposed contributions.\n+ The paper is well organized and provides informative figures.\nWeaknesses:\n- The biggest problem is that the authors do not explain why U-Net is adopted as a baseline model for comparison. This makes experimental comparisons confusing. Did you choose U-net as a CNN structure for comparison?\n- It is better to validate the performance of linear probes on larger datasets since experiments are only evaluated on small MNIST and CIFAR 10 datasets. However, I do not mean that this will be the reason for the rejection of the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "frWkj4wGvbh", "reviewer": "Reviewer_gcLv", "summary": "The authors combine the Vision Transformer architecture with Neural Cellula Automata (NCA, which combines artificial neural networks with cellula automata). They demonstrate that introducing self-attention and positional encodings to NCAs significantly improves performance. One of the main contributions of this work is the authors adaptation of to the global self-attention mechanism to respect the localisation condition for NCAs. The receptive field of individual cells is implicitly grown due to cell updates during CA iterations such that there is a global propagation of information from localised self-attention. This self-organisation is shown to give performance advantages when compared to other architectures. \n\n\n", "questions": "One of the main contributions here is the propagation of local information through CA. However, with large CA systems, I can imagine that there is a separation of timescales between local information propagation and the information being implicitly available to make global changes. Have the authors considered (empirically or theoretically) the rate of information propagation through the system and whether this scales with system size?", "limitations": "As the authors note, there are memory constraints with using recurrent models such as CA, which they offer potential future solutions to. ", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a welcome extension of NCAs to include self-attention and, as such, is highly original. As I understand it, one of the main challenges of achieving this has been how to combine the local computation of NCAs with global updates in ViT, without having highly inefficient learning process. The main contribution from this paper has been an attempt to do exactly this. \n\nThe authors have provided a thorough analysis into the ViTCA, across six benchmark datasets and multiple baseline architectures including ViT, U-Nets and UNetCA. They find that ViTCA can outperform other approaches across on most benchmark datasets. Particularly interesting is the discussion of cell states, as compared to UNetCA, where the authors find that ViTCA is maintains cell stability even when damaged whereas UNetCA diverges. \n\nIn general, I found the manuscript clear and full of information. Some of the figures had almost too much information and it was difficult to relate the caption to the figure. For example, in Figure 2 it took me some time to understand what ‘middle' and 'left,right' exactly referred to. Overall, I thought it was well structured and presented.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept