PaperlayerView exact revision on arXiv

Source-linked AI summary

2D Spatial Reasoning with Adaptive Neural Cellular Automata

Martin Spitznagel, Janis Keuper

arXiv:2610.08518v1cs.CV

TL;DR

Current learning models struggle to use geometric relations for spatial reasoning. The paper introduces adaptive neural cellular automata that adjust their perception across 2D grids. The authors report state-of-the-art results on Sudoku, image-based Sudoku, and maze shortest-path benchmarks.

  • Problem

    Many learning models remain underdeveloped at using geometric information and spatial relations to solve problems.

    Source: §1 · p. 1

  • Method

    Adaptive neural cellular automata use deformable, multi-head perception to adapt the effective neighborhood across grid positions and reasoning steps.

    Source: §4 · p. 5

  • Results

    aNCA surpasses current state-of-the-art 2D spatial-reasoning methods on Sudoku, image-based Sudoku, and maze shortest-path benchmarks.

    Source: §1 · p. 1

  • Takeaways & Limitations

    Learned perceptions are directly inspectable and reveal task-relevant relations such as Sudoku rows, columns, and boxes without explicit architectural encoding.

    Source: §6 · p. 9

    Adaptive perception costs more computation per step than fixed-convolution baselines, and the current architecture targets regular 2D grids.

    Source: §6 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

Spatial reasoning matters across practical tasks, yet current learning models remain underdeveloped at using geometric relations. This paper isolates reasoning on fixed 2D grids and introduces aNCA within a broader literature of task-specific spatial benchmarks and architectures.

1 Introduction

  • Spatial reasoning supports navigation, problem-solving, engineering, and design, while current learning models generally remain underdeveloped at it [2].The paper focuses on reasoning about objects and their positions and movements in space.Source: §1 · p. 1
  • The paper targets the open problem of spatial reasoning on fixed-coordinate 2D grids and introduces aNCA as a learnable cellular automaton for this setting.Its stated contributions include input-dependent, space- and time-variant update rules and improved benchmark performance.Source: §1 · p. 1

1.1 Related Work

  • Prior approaches include pairwise Relation Networks [8], message-passing Scene Graph Neural Networks [10], and spatially gated Vision Transformers.These architectures encode relational structure or data-dependent spatial focus in different ways.Source: §1.1 · p. 2
  • Spatial reasoning is evaluated through task-specific proxies rather than one generally accepted numerical score [2], including 2D Sudoku, maze-path, and global-constraint benchmarks.Other cited work applies image-based SRN diffusion models and Hierarchical Reasoning Models and extensions [6, 21, 22] to 2D tasks.Source: §1.1 · p. 2

2 Neural Cellular Automata

Cellular automata evolve grid states through repeated local updates, and neural cellular automata learn those updates. The section describes perception choices that determine neighborhood communication and illustrates the evaluated tasks.

2 Neural Cellular Automata

  • A cellular automaton updates every cell synchronously from its local neighborhood, while neural cellular automata replace manually specified rules with a learnable network.Traditional rules can have exponentially large search spaces; NCA implementations use shared convolutions to apply learned local rules across positions.Source: §2 · pp. 2–3
  • Figure 1 illustrates how local rules acting on a three-cell neighborhood can generate complex patterns over time.The sketch uses three discrete states and seven update rules.Source: Figure 1 · p. 2

2.1 NCA Perception Modules

  • The perception module determines each cell’s receptive field and communication structure, while the update module maps perceived features to a state increment.The standard convolution baseline limits each step to immediate neighbors, requiring longer-range dependencies to accumulate recurrently.Source: §2.1 · p. 3
  • Dilated convolution enlarges the per-step receptive field without extra parameters, whereas constraint-aligned Sudoku perception uses parallel row, column, and box branches.A dilated 3 × 3 kernel at rate r samples a (2r + 1) × (2r + 1) region; the Sudoku branches encode its three unit types directly.Source: §2.1 · pp. 3–4

2.2 Training NCA

  • Figure 3 presents the four evaluated 2D spatial-reasoning tasks as input-and-target pairs.Each column places the input above its target.Source: Figure 3 · p. 4

3 Spatial Reasoning with NCA

The paper formulates spatial tasks as recurrent computations on 2D grids, using shared training choices and constraint-based objectives. It applies this setup to Sudoku, image-based Sudoku, maze solving, and global color balance.

3 Spatial Reasoning with NCA

  • All tasks use recurrent NCA computation on a 2D grid, with variable-length rollouts, AdamW, gradient clipping, condition channels, and constraint-based objectives that reward valid outputs.The objectives accommodate multiple valid Sudoku completions, shortest-path ties, and color balance without per-pixel supervision.Source: §3 · p. 4
  • Sudoku training masks cells from a million-puzzle dataset and rewards valid row, column, and box digit constraints; image Sudoku uses a frozen codec to reason in latent board space.In the image task, an encoder maps handwritten boards to digit logits and a decoder renders boards back to pixels; a frozen MNIST CNN supplies digit probabilities from decoded tiles.Source: §3 · p. 4, Figure 4 · p. 5
  • Maze solving uses 30 × 30 mazes with wall, start, and goal conditions, while global color balance asks the NCA to meet a prescribed black/white ratio without pixel-level targets.Maze loss combines Dice, binary cross-entropy, and a path-length penalty; color-balance loss combines a global count term with a saturation term.Source: §3 · pp. 4–5

4 Adaptive Neural Cellular Automata (aNCA)

aNCA replaces fixed, space- and time-invariant NCA perception with input-dependent deformable sampling, allowing its effective neighborhood to adapt across grid positions and steps. Its parallel heads use offsets and modulations to gather features, and their learned sampling patterns can be inspected.

Adaptive Perception via Deformable Convolutions

  • aNCA uses a multi-head DCNv2 perception module to make the effective neighborhood adapt across grid positions and NCA steps.This replaces the fixed sampling patterns of standard, dilated, and constraint-aligned convolutions with input-dependent sampling.Source: §4 · p. 5, Figure 5 · p. 5
  • Each deformable kernel tap has a learned position-dependent offset and modulation, with bilinear interpolation resolving fractional sampling locations.The modulation can suppress or amplify a tap independently of its spatial offset.Source: §4 · pp. 5–6
  • Three parallel deformable heads produce complementary sampling patterns, and their explicit offsets make the learned spatial relations inspectable.The update module transforms the gathered features into the next cell state.Source: Figure 5 · p. 5, §4 · p. 6

5 Empirical Evaluation

Across Sudoku, maze, and global color-balance tasks, adaptive perception performs strongly against the compared alternatives, while learned Sudoku sampling patterns align with puzzle constraints. Results also show diverse valid image-Sudoku completions and transfer of the maze solver to unseen structures.

5.1 Solving Sudoku on Array Representations

  • On Hard array Sudoku, aNCA leads on both ASR and ACP, while larger fixed kernels do not improve performance and can be less stable.Learned sampling heat concentrates in the source cell’s row, column, and 3 × 3 box, with heads specializing in complementary directions.Source: Table 1 · p. 6, §5.1 · p. 6, Figure 6 · p. 7

5.2 Solving Sudoku on Images

  • On image Sudoku, aNCA surpasses the 118M-parameter diffusion model and SRM in every difficulty bucket while using fewer parameters.For an underconstrained puzzle, 997/1000 rollouts yield valid completions across 303 distinct boards; for a unique-solution puzzle, resampling varies digit style while preserving the board.Source: Table 2 · p. 7, §5.2 · pp. 7–8, Figure 7 · p. 7

5.3 Solving Maze Puzzles

  • 98.56% Valid Path and 95.2% Valid Optimal: adaptive NCAs lead the compared maze solvers on connectivity and shortest-path metrics while using fewer parameters.Dilated perception reaches 64.30% Valid Optimal; adaptive perception also generalizes to unseen 30 × 30 Prim-style maze structures.Source: Table 3 · p. 8, §5.3 · p. 8, Figure 8 · p. 8

5.4 Learning to Adhere Global Constraints

  • aNCA achieves the highest mean exact-ratio accuracy on global color balance, while the 5 × 5 NCA has the lowest mean count error.Modulated DCNv2 clearly improves exact accuracy over offset-only DCNv1, but gains over the 5 × 5 baseline are smaller and within run-to-run variability.Source: Table 4 · p. 8, §5.4 · p. 8

6 Conclusion

aNCA achieves state-of-the-art results on spatially structured tasks with a fraction of prior methods’ parameters, and its learned perceptions expose task-relevant relations. The conclusion also identifies higher per-step computational cost and a regular-grid scope.

6 Conclusion

  • aNCA sets new state-of-the-art results on Sudoku, image-based Sudoku, and maze solving while using a fraction of prior methods’ parameters.Its learned perceptions reveal task-relevant relations, including Sudoku rows, columns, and boxes, without explicitly encoding them in the architecture.Source: §6 · p. 9
  • The current architecture targets regular 2D grids, and adaptive perception costs more per step than fixed-convolution baselines.Irregular graphs, 3D scenes, and variable-resolution inputs are identified as future directions.Source: §6 · p. 9

AI use statement

  • Generative AI assisted coding and language editing, but was not used to generate research ideas, design the architecture, produce or interpret results, or retrieve or summarize related work.The authors state that they reviewed the AI-assisted text and take responsibility for the final work.Source: AI use statement · p. 9

Ethics statement

  • The study uses public datasets within their intended scope, releases no new dataset, and reports no direct pathway from puzzle solving to harmful application.The authors note that downstream uses of improved spatial reasoning cannot be fully anticipated.Source: Ethics statement · p. 9

Reproducibility statement

  • All reported results are means and standard deviations over multiple independent training runs, and source code with reproducing configurations is slated for release upon publication.The code is planned as a plugin for NCATorch.Source: Reproducibility statement · p. 9

A.1 Video Material

The video material lists demonstrations of Sudoku and MNIST-Sudoku solving and output diversity, maze solving on standard and out-of-distribution instances, and a perception comparison.

A.1 Video Material

  • The Sudoku clips cover batch and hard-instance solving, plus output diversity.The listed clips are “Sudoku: aNCA Solving (Batch),” “Sudoku: aNCA Solving (Hard),” and “Sudoku: aNCA Output Diversity.”Source: §A.1 · p. 12
  • MNIST-Sudoku clips show batch and hard-instance solving, solution diversity, digit-style diversity, and learned spatial relations.The listed clips include “Sudoku MNIST: aNCA Output Diversity (Solutions)” and “Sudoku MNIST: aNCA Output Diversity (Digit Style).”Source: §A.1 · p. 12
  • Maze clips include aNCA solving on 30×30 mazes and out-of-distribution 20×20 DFS and 40×40 Prim mazes.A separate clip lists a 30×30 maze with NCA and a 3×3 convolution.Source: §A.1 · p. 12
  • A separate video is titled “Color Balance Task Perception Comparison.”Source: §A.1 · p. 12

A.2 Implementation Details

The implementation uses PyTorch and torchvision’s standard DCNv2 deformable-convolution implementation, with experiments run on a single NVIDIA RTX 4090.

A.2 Implementation Details

  • All models are implemented in PyTorch, and deformable convolutions use torchvision.ops.deform_conv2d, the standard torchvision DCNv2 implementation.Source: §A.2 · p. 13
  • All experiments were run on a single NVIDIA RTX 4090.Source: §A.2 · p. 13
  • The authors plan to release the code upon publication as a plugin for the NCATorch framework.Source: §A.2 · p. 13

A.2.1 Difference between DCNv1 and DCNv2

Both deformable-convolution variants predict offsets for every kernel tap; DCNv2 also predicts modulation values that scale sampled features.

A.2.1 Difference between DCNv1 and DCNv2

  • DCNv1 and DCNv2 each predict 2k^2 offsets from the current cell state, giving two displacement coordinates per kernel tap.Source: §A.2.1 · p. 13
  • DCNv2 additionally predicts k^2 content-dependent modulation values and weights each sampled feature before aggregation.Source: §A.2.1 · p. 13
  • Zero-initialized offset and modulation predictors make the module initially behave like a regular convolution, with zero offsets and modulation values of one.Source: §A.2.1 · p. 13

A.3.1 Model and Training Hyperparameters

The supplementary sections detail task losses and codec training, then analyze Sudoku perception, image-pipeline accuracy, maze transfer, and global color balance. The reported results include strong Sudoku constraint alignment and transfer to unseen mazes at the training resolution.

A.3.2 Training Loss

  • Sudoku training minimizes squared deviations from one digit per row, column, and 3 × 3 box, plus cross-entropy on given clue cells.The total loss is the sum of the constraint and given-clue losses.Source: §A.3.2 · p. 14

A.3.4 Additional Results: Sudoku

  • All three deformable heads place 81–87% of sampling weight on Sudoku-relevant cells, 3.1–3.4× the 25.9% random baseline.Scores average over 81 source cells and 10,000 held-out puzzles at the final rollout step.Source: Figure 9 · p. 15, Table 7 · p. 16, §A.3.4 · p. 16

A.4.2 Codec Training Loss

  • The Sudoku codec decoder uses a weighted composite loss combining KL, pixel, feature, classifier, total-variation, ink, and binarization terms.Feature L1 compares pooled frozen-classifier features of rendered and target cell crops; classifier cross-entropy rewards legible digits.Source: §A.4.2 · p. 18

A.4.3 Codec Accuracy

  • The encoder reaches 99.38% per-cell accuracy on clue cells, but only 74.58% of boards have every clue recognized correctly.Despite imperfect inputs, aNCA maintains strong downstream solving performance without additional training.Source: §A.4.3 · p. 18
  • The decoder achieves 100% per-cell accuracy and a 100% perfect round-trip rate, so decoder errors contribute zero to pipeline failures.ASR is evaluated against ground-truth clue digits, while encoder misrecognitions can still affect NCA conditioning.Source: §A.4.3 · p. 18

A.5.2 Training Loss

  • Maze training combines binary cross-entropy, Dice overlap, and a normalized path-length penalty, with the length term weighted by 0.05.Walls are excluded from the loss because they are trivially predictable from the condition input.Source: §A.5.2 · p. 20

A.5.3 Additional Results: Mazes

  • 100% Valid Path and 99.4% Valid Optimal on 1,000 unseen Prim-generated 30 × 30 mazes, without finetuning.The mazes differ from the training distribution in wall density and corridor geometry.Source: Table 11 · p. 21, §A.5.3 · p. 21

A.6.2 Training Loss

  • Global color balance uses a count loss to match the prescribed pixel mean and a saturation loss to push pixels toward black or white.The task requires a prescribed black/white ratio without per-pixel supervision.Source: §A.6.2 · p. 22, Figure 10 · p. 23
Loading 2610.08518v1…