Reasoning with Neural Cellular Automata
Mayalen Etcheverry, Pietro Miotti, Aidan Sirbu, Konstantin Schürholt, Mariia Drozdova, Arna Ghosh, Blaise Agüera y Arcas, James Manyika, Blake Richards, Eyvind Niklasson
cs.LG, cs.AI, cs.MA, nlin.CG
2026-09-29
Google shows neural cellular automata, grids of cells seeing only 3x3 neighbors, can solve mazes, Sudoku and ARC-AGI: 100% on 201x201 mazes with 44x fewer FLOPs than DeepThink.
Mainstream reasoning architectures, from looped transformers to compact recurrent reasoners like TRM and LoopViT, all assume two things: every unit can attend to every other unit, and updates happen in global lockstep. That wiring drives data movement and energy cost, and it ties these models to centralized hardware. The Google Paradigms of Intelligence team asked a more basic question: if each computing unit can only see its 3×3 neighborhood, and cells fire asynchronously, can the system still do multi-step reasoning? Prior NCA work had only managed 12.9% on a 262-task ARC subset, with one model trained per task. This paper runs strictly local architectures through large mazes, Sudoku, ARC-AGI-1, and pixel-level Sudoku, and the answer is largely yes.
An NCA (Neural Cellular Automaton) treats an H×W grid as the computer. Each cell holds a C-dimensional state vector split into slices: an immutable input slice holds the puzzle (in mazes it spans all channels to block information from crossing walls; in Sudoku it clamps the given clues), an output slice readable at any step, a hidden slice for latent computation, and for ARC a learned task-embedding slice.
Each step is two operations: a perception module compresses the 3×3 neighborhood into a vector, and a weight-tied MLP shared by all cells produces a residual update. A Bernoulli firing mask gates each update, so cells fire asynchronously and stochastically. The same weights are shared across all of space and time, which is why 10K parameters suffice.
Three choices carry the paper:
On ARC, the global time embedding used in training is replaced at inference by per-cell counters that tick only when the cell fires; swapping the task embedding makes one model execute different transformations on the same unseen input, which is task-conditioned program induction rather than memorization.
| Benchmark | Baseline | NCA |
| Maze-OOD 201×201 | DeepThink: 784K params, 521.7T FLOPs, 74.0% | 10K params, 11.8T FLOPs, 100% |
| Maze-Hard | PTRM: 7M params, 382.2T FLOPs, 86.7% | 41K params, 2.0T FLOPs, 89.2% |
| Sudoku-OOD | AKOrN: 89.5% (97.3T FLOPs) | 98.5% (23.9T) |
| Sudoku-Extreme | PTRM: 98.8% | 92.7%, NCA trails here |
| ARC-AGI-1 | TRM 44.6%, LoopViT-l 65.8% (both pass@2) | 48.8% pass@2, 60.3% pass@64, 63.0% with a 3-model ensemble |
The secondary results are equally solid: trained only on boards with at least 31 clues, it solves 17-clue Sudokus with parallel rollouts; a 9×9 maze model trained in 3 TPU-minutes transfers to mazes up to 500× larger with no weight updates; cells above 0.95 confidence drop their firing rate to 0.4, cutting total cell updates by 30%, and after mid-rollout damage the adaptive variant recovers at 0.52× the cumulative operations; test-time noise injection does not hurt and even helps. On Visual Sudoku (256×256 handwritten boards, where classification, solving, and rendering happen in one model), it reaches 87.8% on easy boards and 18.9% on hard ones.
The dynamics are the interesting part. In mazes, activations spread like a wavefront and dead ends get pruned by local backtracking waves. On extreme Sudoku, cells reach a near-valid grid, deliberately increase constraint violations to escape the local minimum, then converge to a globally consistent solution. The authors call this a visible 'spatial chain-of-thought'.
Strict locality is not a barrier to multi-step reasoning. That is the core claim, and it comes with unusually strong efficiency evidence: 10K parameters covering a 201×201 maze at 1/44 of DeepThink's FLOPs. Fully shared weights map naturally onto low-power, decentralized, fault-tolerant hardware that global-attention models cannot target. The three-axis test-time scaling plus pruning is a reusable recipe for compute allocation in any recurrent reasoner, and the reasoning process is directly visible in the grid, which beats a black box for interpretability. The honest caveat: on Sudoku-Extreme and ARC it does not beat the strongest globally connected baselines, and the authors position the work as a feasibility study, not a leaderboard run.
The authors list three: training is still non-local (BPTT with a global loss), so only inference is decentralized; parallel rollouts amount to random search rather than active exploration; and strict locality imposes propagation delays that make long-range dependencies a bottleneck. Two more from a close read: locality costs iterations (D=13000 versus DeepThink's 2000 on the largest mazes), a liability in latency-sensitive settings; and Visual Sudoku manages only 18.9% on hard boards with a memory-hungry training pipeline, so pixel-space reasoning remains a proof of concept. The bigger issue is that every benchmark here is a grid-structured puzzle, exactly the inductive bias locality wants. Whether the framework keeps any edge on reasoning without spatial structure, such as math or code, goes untested.