Reasoning with Neural Cellular Automata

gist

Etcheverry, Miotti, Sirbu, and coauthors show Neural Cellular Automata (NCAs) with local asynchronous updates solve mazes, Sudoku, and ARC-AGI-1. Compact shared-rule grids produce visible spatio-temporal reasoning and can generalize out of distribution when test-time compute expands across space, time, or parallel trials. Sample replay and stochastic perturbations are required for that generalization, and noise at test time still helps. The models also allocate compute adaptively after damage and can solve Visual Sudoku in raw 256×256 pixel space.

ideas

• Local, asynchronous cells can solve hard visual reasoning tasks. Weight-tied NCAs with 3×3 perception reach strong accuracy on Maze-OOD, Maze-Hard, Sudoku-OOD, Sudoku-Extreme, and ARC-AGI-1 with far fewer parameters than global recurrent baselines, while needing more rollout steps.
• Test-time compute expands along three axes. Parallel stochastic trials, longer rollouts, and larger grids improve out-of-distribution accuracy; Niche-Capped Diversity Pruning cuts redundant trajectories and can raise accuracy at fixed FLOPs by reallocating breadth into depth.
• Sample replay and perturbations unlock generalization. Ablations show replay, damage, noise, and target-swap during training, plus asynchronous updates on Sudoku, are required for hard out-of-distribution boards; injecting noise at test time further raises accuracy.
• Adaptive fire rates concentrate compute where it is needed. On extra-large mazes, lowering update probability for confident cells cuts total cell updates and speeds recovery after mid-rollout damage.
• Pixel-space Visual Sudoku is a proof of concept. An off-the-shelf NCA on 256×256 MNIST Sudoku images solves 87.8% of easy and 18.9% of hard boards, with intermediate frames showing classification then iterative digit consensus.

quotes