2D Spatial Reasoning with Adaptive Neural Cellular Automata

Martin Spitznagel; Janis Keuper

cs.CVOct 6, 2026

2D Spatial Reasoning with Adaptive Neural Cellular Automata

Authors: Martin Spitznagel, Janis Keuper

Organizations: Institute for Machine Learning and Analytics (IMLA), Offenburg University, Germany · University of Mannheim, Germany

Abstract

Many modern learning approaches are still struggling with spatial reasoning tasks, i.e. they lack the ability to utilize geometric information of perceived entities and their spatial relation to each other to solve problems. We introduce a novel Adaptive Neural Cellular Automata (aNCA) architecture which uses deformable convolutions to dynamically adapt the perceptive field and iteratively reason over 2D spatial relations on grid-like data structures (e.g. images). Empirical results on public benchmarks show state of the art comprehensible results with high generalization abilities for solving image based puzzles like Sudoku or finding the shortest path in a maze.

Figures & tables

Figure 1: Sketch of a basic 1D Cellular Automaton with three discrete states $s_{i}\in\{0,1,2\}$ and seven update rules $\mathcal{R}$ , which operate on the sum over a 3-cell neighborhood $\mathcal{N}$ . a) shows the inference of complex patterns from an initial state by the rules visualized in b) over time.

Figure 2: Sketch of a basic CNN implementation [ 34 ] of a 2D NCA with a 3D state space. The perception module processes the cell state using one of several configurable perception options. The update module processes the perceived features to compute state updates. Stochastic updates are applied before updating the visible and hidden channels to form the new cell state for the next iteration. The sample pool is used after one batch of images is processed to retain and reuse evolved states for subsequent training iterations.

Figure 3: The four 2D spatial reasoning tasks evaluated in this work. Each column shows the input (top) and target (bottom).

Figure 4: Latent pixel Sudoku pipeline. The encoder $E_{\psi}$ maps the initial handwritten Sudoku image into a $9\times 9\times 9$ grid of digit logits, the NCA iterates in this latent board space under the Sudoku constraint loss until a valid completion emerges, and the decoder $D_{\omega}$ renders the final board back to pixels. Freezing $E_{\psi}$ and $D_{\omega}$ decouples perception from reasoning and allows different NCA variants to be evaluated within the same image-space pipeline.

Panel of Figure 5 — Figure 5: (a) Comparison of perception sampling patterns: standard $3\times 3$ , dilated, constraint-aligned, and deformable convolution. (b) One aNCA update step: the perception module $\mathcal{P}_{\phi}$ predicts offsets $\Delta\mathbf{p}_{n}(\mathbf{p})$ and modulations $m_{n}$ from $s_{t}$ , which guide the deformable convolution to aggregate features from adaptive grid locations. The update module $\mathcal{U}_{\phi}$ then produces the next state $s_{t+1}$ .

Perception	Easy [1, 27]		Medium [28, 54]		Hard [55, 81]		Param.
Perception	ASR	ACP	ASR	ACP	ASR	ACP
NCA w. 3x3 Conv.	100 $\pm$ 0	100 $\pm$ 0	86.35 $\pm$ 1.00	98.85 $\pm$ 0.13	78.23 $\pm$ 1.84	98.63 $\pm$ 0.10	50k
NCA w. 5x5 Conv.	100 $\pm$ 0	100 $\pm$ 0	87.47 $\pm$ 1.65	98.93 $\pm$ 0.12	75.03 $\pm$ 8.38	96.27 $\pm$ 4.05	105k
NCA w. 7x7 Conv.	100 $\pm$ 0	100 $\pm$ 0	82.70 $\pm$ 1.62	98.43 $\pm$ 0.21	76.95 $\pm$ 2.07	98.43 $\pm$ 0.15	189k
NCA w. 9x9 Conv.	100 $\pm$ 0	100 $\pm$ 0	71.58 $\pm$ 18.82	95.88 $\pm$ 4.41	39.80 $\pm$ 37.15	84.95 $\pm$ 19.71	300k
NCA w. R/C/B Conv.	100 $\pm$ 0	100 $\pm$ 0	87.38 $\pm$ 2.64	98.90 $\pm$ 0.22	78.18 $\pm$ 2.81	98.58 $\pm$ 0.19	145k

Table 1: Sudoku on the array representation, reported as mean

\pm

standard deviation over four training runs per perception. Best Hard-bucket ASR/ACP in bold.

Panel of Figure 6 — Figure 6: Learned sampling reach of each deformable perception head from two interior source cells (black-bordered squares at grid positions $(3,3)$ and $(4,4)$ ). Each panel is one head: the heatmap shows the fraction of the head’s total sampling weight placed on every cell of the $9\times 9$ board, aggregated over held-out test puzzles at the final NCA step. Dashed overlays mark the source cell’s row (green), column (orange), and $3\times 3$ box (purple). The learned heat concentrates inside these overlays and the three heads specialize to complementary constraint directions.

Method	Easy	Medium	Hard
Method	[1, 27]	[28, 54]	[55, 81]	Param.
Diffusion Model	99.4	53.6	0.8	118M
SRM	99.8	75.4	51.6	118M
				Codec + NCA
NCA 3x3 Conv.	99.40 $\pm$ 0.14	80.90 $\pm$ 0.90	71.98 $\pm$ 1.61	1.1M + 50k
NCA 5x5 Conv.	99.13 $\pm$ 0.50	79.97 $\pm$ 1.70	69.00 $\pm$ 6.63	1.1M + 105k

Table 2: MNIST Sudoku. Results in ASR (Average Solve Rate), reported as mean

\pm

standard deviation over four training runs. Best Hard-bucket ASR in bold. Per-bucket ACP is reported in table 9 .

Panel of Figure 7 — Figure 7: Output diversity of the Sudoku codec. (a) For an underconstrained clue pattern with at least $10^{6}$ valid completions, repeated stochastic NCA rollouts produce multiple distinct valid solutions. (b) For a puzzle with a unique solution, resampling the decoder style latent preserves the solved board while varying the digit style.

Panel of Figure 8 — Figure 8: (a) Maze solving: the model receives walls (black), start (green), and goal (red). Blue cells indicate correct path predictions matching the target; yellow cells are predicted path pixels that deviate from the target. (b) Generalization to unseen $30\times 30$ Prim-style maze structures.

Method	Source	Valid Path	Valid Optimal	Param.
HRM	[ 6 ]	– ⋆	74.5%	27M
ItrSA++	[ 21 ]	– ⋆	78.6%	3M
TRM-Att	[ 22 ]	– ⋆	85.3%	7M
NCA w. 3x3 Conv.	Ours	2.54 $\pm$ 0.84	0.08 $\pm$ 0.08	50k
NCA w. 5x5 Conv.	Ours	24.78 $\pm$ 1.68	10.78 $\pm$ 1.21	105k
NCA w. Dilated Conv.	Ours	74.26 $\pm$ 1.07	64.30 $\pm$ 1.32	150k

Table 3: Maze solving on

30\times 30

grids, reported as mean

\pm

standard deviation over five training runs. Valid Path checks connectivity and wall avoidance. Valid Optimal additionally requires shortest-path length.

Perception	Source	Imbalance $\downarrow$	Accuracy $\uparrow$	Param.
Diffusion	[ 7 ]	1.27	25.0%	19.7M
SRM	[ 7 ]	0.53	51.8%	19.7M
NCA w. 3x3 Conv.	Ours	1.13 $\pm$ 0.17	26.0% $\pm$ 5%	48k
NCA w. 5x5 Conv.	Ours	0.07 $\pm$ 0.06	95.3% $\pm$ 2%	100k
NCA w. DCNv1	Ours	1.61 $\pm$ 0.59	18.7% $\pm$ 11%	147k
aNCA	Ours	0.1 $\pm$ 0.08	96.8% $\pm$ 3%	152k

Table 4: Global color balance. NCA results are mean

\pm

standard deviation across independent training runs. Imbalance measures absolute color-count error. Accuracy measures exact satisfaction of the

50/50

ratio.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Category	Hyperparameter	Value
NCA state	Cell channels	24
NCA state	Positional embeddings	yes
Update network	Architecture	MLP ( $1{\times}1$ Conv), 1 hidden layer, 128 channels
Optimization	Optimizer	AdamW
	Learning rate	$4\times 10^{-4}$
	LR schedule	WSD (warmup–stable–decay)

Appendix

Table 5: Hyperparameters shared across all NCA variants for the Sudoku task. Perception-specific settings (kernel size, dilation, number of deformable heads) vary per variant and are described in section 2 .

Variant	Params	Train VRAM (MB)	Infer VRAM (MB)	Infer ms / puzzle
NCA w. 3x3 Conv.	50k	303.1	0.5	159.64
NCA w. 5x5 Conv.	105k	311.9	0.9	166.38
NCA w. R/C/B Conv.	145k	610.3	1.0	251.04
NCA w. Dilated Perc.	150k	480.8	1.2	238.28
aNCA	165k	1139.6	17.7	832.75

Appendix

Table 6: Resource usage of the Sudoku NCA variants. Training VRAM is the peak CUDA memory allocated during a representative training step (batch size

128

, rollout length

24

). Inference VRAM and runtime are measured at batch size

1

with a rollout of

1500

steps on an NVIDIA RTX 4090. Inference time is averaged per puzzle over repeated runs after warm-up.

Panel of Figure 9 — Figure 9: Learned sampling distance distributions of the three deformable perception heads (A, B, C) at the final NCA step, aggregated over held-out test puzzles. Each plot shows how far each kernel tap reaches from the source cell, revealing that the heads develop complementary routing strategies: some taps remain local while others extend to capture row, column, or box constraints.

Head	Row%	Col%	Box%	Union%	Enrichment
Head 1	20.7	32.6	47.5	81.0	3.13 $\times$
Head 2	61.1	59.6	69.6	86.9	3.35 $\times$
Head 3	53.0	45.8	54.3	83.5	3.22 $\times$
Random baseline	–	–	–	25.9	1.00 $\times$

Appendix

Table 7: Per-head constraint alignment at the final NCA step, averaged over all 81 source cells and 10 000 test puzzles. Union% is the fraction of weight on the source cell’s row

\cup

column

\cup

box. Random baseline is the expected Union% under uniform sampling (

25.9\%

Category	Hyperparameter	Value
Encoder $E_{\psi}$	Base channels	32
Encoder $E_{\psi}$	Hidden dim	128
Decoder $D_{\omega}$	Base channels	64
	Hidden dim	128
	Style latent dim	8
Optimization	Optimizer	AdamW

Appendix

Table 8: Architecture and training hyperparameters for the Sudoku codec. Encoder and decoder are trained independently with AdamW.

Method	Source	Easy [1, 27]		Medium [28, 54]		Hard [55, 81]		Param.
Method		ASR	ACP	ASR	ACP	ASR	ACP
Related Work
Diffusion Model	[ 7 ]	99.4%	– ⋆	53.6%	– ⋆	0.8%	– ⋆	118M
SRM	[ 7 ]	99.8%	– ⋆	75.4%	– ⋆	51.6%	– ⋆	118M
NCAs
NCA w. 3x3 Conv.	Ours	99.40 $\pm$ 0.14	99.90 $\pm$ 0.00	80.90 $\pm$ 0.90	98.33 $\pm$ 0.10	71.98 $\pm$ 1.61	98.20 $\pm$ 0.08	1.1M + 50k

Appendix

Table 9: Sudoku Images

Category	Hyperparameter	Value
NCA state	Cell channels	24
	Positional embeddings	no
	Fire rate	0.5
Update network	Architecture	MLP ( $1{\times}1$ Conv), 1 hidden layer, 128 channels
Optimization	Optimizer	AdamW
	Learning rate	$1\times 10^{-3}$

Appendix

Table 10: Hyperparameters shared across all NCA variants for the maze task. Perception-specific settings vary per variant and are described in section 2 .

Test Maze Size	Generator	Valid Path	Valid Optimal
$30\times 30$	Sapient	98.56%	94.18%
$20\times 20$	Prim	100%	100%
$30\times 30$	Prim	100%	99.4%

Appendix

Table 11: Generalization of the deformable aNCA maze solver to a different maze distribution at the training resolution. The model is trained on

30\times 30

Sapient mazes and evaluated without finetuning on 1000 mazes per test distribution. Valid Path checks connectivity and wall avoidance. Valid Optimal additionally requires shortest-path length.

Category	Hyperparameter	Value
NCA state	Cell channels	24
	Positional embeddings	no
	Fire rate	0.5
Update network	Architecture	MLP ( $1{\times}1$ Conv), 1 hidden layer, 128 channels
Optimization	Optimizer	AdamW
	Learning rate	$3\times 10^{-4}$

Appendix

Table 12: Hyperparameters for the global color balance task.

Figure 10: Global color balance: the model must satisfy a prescribed black/white ratio without per-pixel supervision.

Explore similar work

Reasoning with Neural Cellular Automata
Sep 28, 2026Mayalen Etcheverry, Pietro Miotti, Aidan Sirbu +7Neural Cellular Automata Brain-Inspired Synergistic Framework
Google Paradigms of Intelligence Team · School of Computer Science, McGill University · Mila - Quebec AI Institute +4
Applications of Neural Cellular Automata: State of the Art, Challenges and Opportunities
Sep 21, 2026Nick Lemke, Niklas Ihm, John Kalkhof +11Neural Cellular Automata Medical Images
Technical University of Darmstadt, Darmstadt, Germany · ImFusion GmbH, Munich, Germany · Inria Center at University Cˆote d’Azur, Sophia Antipolis, France +9
Architecture Generalization with MetaNCA
Jul 8, 2026Meet Barot, Daniel Berenberg, Sina KhajehabdollahiNeural Cellular Automata Brain-Inspired Synergistic Framework
Mythos Scientific, New York, USA · Independent Scholar

Sep 28, 2026, cs.LGJ/K move · Enter open · S save

Reasoning with Neural Cellular Automata

Mayalen Etcheverry, Pietro Miotti, Aidan Sirbu, Konstantin Schürholt+6

Google Paradigms of Intelligence Team · School of Computer Science, McGill University · Mila - Quebec AI Institute+4

Neural Cellular Automata Brain-Inspired Synergistic Framework Visual Reasoning

Open paper AskPDF arXiv

Modern AI architectures used to solve visual reasoning tasks typically rely heavily on global connectivity and synchronization. As biological systems demonstrate, though, sophisticated computation can be performed in a more decentralized fashion. In this work, we test the reasoning capabilities of Neural Cellular Automata (NCAs), networks of recurrent cells that use strictly local connectivity and asynchronous updates. NCAs have been extensively studied in artificial life experiments, but it is unclear whether they can perform complex multi-step reasoning. We show that NCAs produce spatio-temporal dynamics capable of solving challenging visual reasoning tasks, including large mazes, Sudoku, and ARC-AGI-1. Furthermore, we provide evidence that NCAs generalize out-of-distribution when running with larger grids, longer rollouts, or parallel trials; and that the latter can be made more efficient via pruning of redundant trajectories. We find that these generalization capabilities depend on training with sample replay and stochastic perturbations, and that stochasticity remains beneficial at test time. Finally, we show that NCAs are robust reasoners capable of dynamically modulating compute to recover efficiently from damage, and that they can scale to solve reasoning in raw pixel space.

Abstract

Explore similar work

Reasoning with Neural Cellular Automata

Applications of Neural Cellular Automata: State of the Art, Challenges and Opportunities

Architecture Generalization with MetaNCA