All summaries · 2026-10-07

2D Spatial Reasoning with Adaptive Neural Cellular Automata

Martin Spitznagel, Janis Keuper

arXiv:2610.08518 · abstract · pdf · summarized by meta/muse-spark-1.3-contributor on 2026-10-07

The one-paragraph version

This paper asks whether a very small, iterative grid model can learn to reason about space. The authors start from Neural Cellular Automata, meaning a grid of cells where every cell holds a little memory vector and repeatedly updates itself by looking at its neighbors. Standard versions always look at the same fixed neighbors, like the eight cells around you. The new proposal, called Adaptive Neural Cellular Automata or aNCA, lets each cell learn where to look on each step, depending on what it currently sees. On four 2D grid puzzles — symbolic Sudoku, image-based Sudoku made of handwritten digits, shortest-path finding in 30-by-30 mazes, and making a picture with an exact 50/50 black-white count — this adaptive looking wins. It solves more hard Sudokus, finds more valid shortest paths, and matches global counts, while using roughly 50k to 256k parameters versus 3M to 118M for prior diffusion, spatial reasoning, and hierarchical reasoning baselines. Crucially, you can inspect where it looked and see that for Sudoku it rediscovered rows, columns, and 3-by-3 boxes without being told to.

The problem they're solving, and why it matters

Spatial reasoning here means using geometry to solve a problem: how objects relate in position, what constrains what, and how those relations change as you fill things in. The paper follows a taxonomy called DISE, which divides tasks into Intrinsic versus Extrinsic and Static versus Dynamic. Intrinsic is about one object itself, like its shape. Extrinsic is about relations between multiple objects in a scene. Static means the scene is fixed. Dynamic means relations change over time. They target 2D Extrinsic problems on a fixed x-y grid.

Two examples make this concrete. Finding the shortest path in a maze is Extrinsic-Static: walls, start, and goal stay fixed, but you must relate distant locations through free space. Solving Sudoku is Extrinsic-Dynamic in their framing: each time you decide a digit, the constraints on all related cells change.

This matters because many current models, including fluent multimodal large language models, show what the authors call a semantic-to-geometric gap. They can say the words “left of” or “in the same row,” but fail to keep a coherent geometric model and do multi-step simulation. Rather than building a large top-down World Model that tries to predict whole futures at once, the authors take a bottom-up approach: isolate clean 2D tasks where the needed spatial relations are unambiguous, and test whether a minimal iterative architecture can learn the reasoning procedure itself.

The key idea, in plain words

Imagine Sudoku as a neighborhood gossip problem. To decide if a “7” can go in a cell, you need to hear from its entire row, its entire column, and its 3-by-3 box. A standard Neural Cellular Automata cell is near-sighted: per step it only hears its immediate 3-by-3 neighbors, and long-range news must hop cell-to-cell over many steps.

The authors first try obvious fixes: use a bigger fixed window like 5-by-5 or 9-by-9, use a dilated window that samples with gaps to see farther for free, or hand-build row-shaped, column-shaped, and box-shaped sensors for Sudoku. Those help a little but do not learn which distant cells matter for this puzzle at this moment.

The key idea is to make perception adaptive. Each cell predicts small shifts, called offsets, that bend its sensor taps toward useful places, plus a volume knob, called modulation, that turns each tap up or down. So on one step a cell in the middle of a Sudoku board might stretch one head mostly left-right to check its row, another head up-down to check its column, and a third head into its box. On a maze, the same mechanism can learn to follow corridors and ignore walls. Because the model uses three parallel deformable heads, different heads can specialize to different directions. And because those look-where decisions are numbers you can plot, the reasoning becomes inspectable: you can draw heatmaps of where each cell actually sampled.

How it actually works, step by step

Think of the system as a grid that thinks by repeatedly rewriting itself.

First, state. Every grid position holds a state vector, meaning a list of about 24 numbers that mix memory and current guess. For Sudoku, that includes nine channels for digit beliefs. For mazes, it includes a path belief. At every step the original puzzle clues — given digits, or walls plus start and goal — are glued back on as extra channels, so the model never forgets the evidence. This glued-on input is called conditioning.

Second, perception. This is the “look around” stage. The baseline uses one learnable convolution, meaning a small weighted window slid identically everywhere. The proposed version uses deformable convolution version 2, or DCNv2 for short. In words: a normal 3-by-3 sensor has nine fixed tap positions around you. A deformable sensor starts from those nine positions, then adds a learned shift to each tap, predicted from the current state. Fractional landing spots are filled in by blending nearby cells, which is bilinear interpolation. DCNv2 also predicts a modulation weight between 0 and 2 for each tap, so a tap can be silenced or amplified. The older DCNv1 variant tested in the paper only shifts, without that volume knob.

Third, update. The gathered neighborhood features go into a tiny shared network, essentially a one-hidden-layer perceptron applied with 1-by-1 convolutions, meaning it acts separately at each cell without further spatial mixing. It outputs a small change that is added to the cell’s state. The same rule is applied everywhere and repeated for many steps.

Fourth, training for stability. They unroll the recurrence for a random number of steps, typically 18 to 24 during training and much longer at test time, up to 1,500 for Sudoku and 100 for mazes, then compare to a goal. For Sudoku they do not force one specific solution, because hard puzzles can have many. Instead they use a constraint loss: for every row, column, and box, each digit should appear once in total probability, plus the given clues must match. For mazes they combine overlap and classification terms on non-wall cells plus a small penalty if the predicted path length differs from the true shortest length. For color balance they push the global mean toward the target ratio and push each pixel to commit to black or white. They train with the AdamW optimizer, and they reuse old intermediate grids from a sample pool, meaning a buffer of past states mixed into new batches, so the rule learns not to blow up on long rollouts.

For image Sudoku, they avoid training vision and reasoning together. They pretrain a separate codec: an encoder that maps handwritten tiles to a 9-by-9-by-9 digit-logit board, and a decoder that is a conditional variational autoencoder with a style code that renders a board back to pixels. The NCA reasons only in that board space, then the decoder draws the result.

What they showed — results, honestly, with limitations

On symbolic Sudoku, tested on held-out puzzles grouped into Easy with 1 to 27 cells removed, Medium with 28 to 54, and Hard with 55 to 81, all variants ace Easy. The gap appears on Hard. The paper reports Average Solve Rate, meaning fraction of puzzles ending in a fully valid completion, and Average Cell Precision, meaning fraction of filled cells consistent with a valid completion. On Hard, aNCA reaches about 87.8% solve rate and 99.2% cell precision, versus about 78.2% and 98.6% for the standard 3-by-3 NCA. Enlarging the fixed window to 7-by-7 or 9-by-9 does not fix this; the 9-by-9 version collapses to about 39.8% on Hard and is wildly unstable across seeds, plus or minus 37 points. That supports the claim that gain is not just bigger receptive field or more parameters.

Interpretability is unusually direct. Aggregated over 10,000 test puzzles, each deformable head places 81 to 87% of its sampling weight inside the source cell’s row, column, or box combined, compared to 25.9% expected under uniform random sampling — roughly a 3.1 to 3.4 times enrichment. Different heads favor row versus column versus box, visible in heatmaps from cells like (3,3) and (4,4).

On MNIST Sudoku, where each cell is a handwritten glyph, they reuse the exact same NCA checkpoints inside the frozen codec pipeline and judge the final image with a frozen digit classifier. aNCA gets about 82.1% solve rate on Hard, versus 51.6% for the prior SRM model and 0.8% for a diffusion baseline, both at 118M parameters, versus 1.1M for the shared codec plus 165k for aNCA. They also show diversity: on a puzzle stated to have at least a million completions, 1,000 stochastic rollouts yield 997 valid completions and 303 distinct boards. On a unique-solution puzzle, the board stays the same while digit stroke style varies when the decoder style code is resampled.

On 30-by-30 mazes, the metrics are Valid Path, meaning start connects to goal without crossing walls, and Valid Optimal, meaning length matches the shortest path. Local 3-by-3 perception almost never connects, about 2.5% valid. Dilated perception reaches about 64.3% optimal. aNCA reaches about 98.6% valid and 94.2% optimal, ahead of reported optimal scores of 74.5% for HRM at 27M, 78.6% for ItrSA++ at 3M, and 85.3% for TRM-Att at 7M. Without retraining, the same checkpoint gets 100% valid and 99.4% optimal on 1,000 procedurally different Prim-style mazes at the same size, plus 100% on 20-by-20 Prim mazes. That is same-resolution distribution shift, not larger-grid scaling, which the paper does not claim.

On global color balance with no per-pixel target, just “make it 50/50,” aNCA gets about 96.8% exact-ratio accuracy with mean count error 0.1, versus 51.8% and 0.53 for SRM and 25.0% and 1.27 for diffusion. Honestly, the 5-by-5 fixed NCA is essentially tied at 95.3% accuracy and even lower mean error at 0.07, within run variation, so adaptivity helps less here. The clearer win is DCNv2 over offset-only DCNv1, which falls to 18.7%.

Limitations are stated and measurable. Adaptive perception costs more per step: about 833 milliseconds per Sudoku puzzle and 17.7 MB inference memory versus about 160 milliseconds and 0.5 MB for 3-by-3, and about 1140 MB versus 303 MB peak training memory. There is still seed variability. The encoder alone correctly recognizes every clue in only 74.58% of boards, so the reasoner is working from noisy inputs, though the decoder round-trip is reported as perfect. All work is on regular 2D grids; irregular graphs, 3D, and variable resolution are left as future work.

Why this might matter to me

For spatial reasoning in LLMs and VLMs, the lesson is architectural: dynamic, query-dependent routing beats a bigger fixed window. Current vision transformers often add locality biases or decay, but they still struggle with multi-hop constraint propagation and working memory. aNCA shows that a tiny recurrent unit that learns where to read from at each iteration can enforce row-like, line-of-sight, or corridor-following relations without hard-coding them. That suggests a useful auxiliary module or training probe for grounding words like “aligned,” “between,” or “connected” in explicit sampling maps you can audit, rather than attention maps you hope correlate.

For world models, the paper is an explicit counterpoint to top-down prediction. It isolates iterative simulation: keep the observation clamped, refine a latent board, and supervise validity rather than one exact future. That is relevant if you want planners that can produce any valid plan under constraints, with diversity over completions, not just imitation of a demonstration trajectory.

For text-to-CAD and parametric geometry, Sudoku rows and maze walls are a 2D stand-in for constraints like coincidence, parallelism, symmetry, and containment. The codec split is the most transferable pattern: a perception front-end maps sketch pixels or primitives to a symbolic parameter board, a small iterative solver enforces global constraints, and a decoder renders back. The modulation knob matters here because different constraint families need different taps to be silenced per entity — much like suppressing irrelevant mates in an assembly.

For 3D generation and scene representation, do not read this as a 3D method. Read it as evidence that learned long-range, content-adaptive neighborhoods plus constraint losses can replace huge denoising backbones on structured tasks, and that sampling locations themselves are a compact, interpretable scene relation graph. Extending offsets to voxel grids, triplanes, or graph neighborhoods, and learning box-like or symmetry-aligned heads from data, would be the natural bridge — but the paper provides no 3D results, so that remains a hypothesis to test.

Terms worth knowing