Probing the Inductive Bias of Neural Networks through Learning Random Cellular Automata

Jan Disselhoff, Michael Wand
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:25483-25509, 2026.

Abstract

Why do neural networks generalize well on natural data? Natural data originates from processes subject to specific physical constraints, such as temporal and spatial invariance, that make it easier to learn. We investigate the sufficiency of these properties using 2D cellular automata as a controlled testbed: systems that are perfectly local, symmetric, and deterministic. We find that these conditions alone are not sufficient to predict the $k$-step evolution of a cellular automaton. We then examine smoothness (average sensitivity) as an additional criterion and find it predictive but still incomplete. Finally, we introduce a circuit complexity perspective, hypothesizing that natural functions are computable by small circuits. Junta coefficients, measuring the concentration of Fourier weight by interaction degree, provide a tighter predictor of learnability and a correspondence to combinatorial complexity. Across architectures (CNNs, transformers, MLPs), learnable functions are predominantly those with spectral weight concentrated at low degrees and therefore low complexity. These results would be consistent with the hypothesis that natural data is learnable because natural dynamics filters out complex, high-degree interactions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-disselhoff26a, title = {Probing the Inductive Bias of Neural Networks through Learning Random Cellular Automata}, author = {Disselhoff, Jan and Wand, Michael}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {25483--25509}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/disselhoff26a/disselhoff26a.pdf}, url = {https://proceedings.mlr.press/v306/disselhoff26a.html}, abstract = {Why do neural networks generalize well on natural data? Natural data originates from processes subject to specific physical constraints, such as temporal and spatial invariance, that make it easier to learn. We investigate the sufficiency of these properties using 2D cellular automata as a controlled testbed: systems that are perfectly local, symmetric, and deterministic. We find that these conditions alone are not sufficient to predict the $k$-step evolution of a cellular automaton. We then examine smoothness (average sensitivity) as an additional criterion and find it predictive but still incomplete. Finally, we introduce a circuit complexity perspective, hypothesizing that natural functions are computable by small circuits. Junta coefficients, measuring the concentration of Fourier weight by interaction degree, provide a tighter predictor of learnability and a correspondence to combinatorial complexity. Across architectures (CNNs, transformers, MLPs), learnable functions are predominantly those with spectral weight concentrated at low degrees and therefore low complexity. These results would be consistent with the hypothesis that natural data is learnable because natural dynamics filters out complex, high-degree interactions.} }
Endnote
%0 Conference Paper %T Probing the Inductive Bias of Neural Networks through Learning Random Cellular Automata %A Jan Disselhoff %A Michael Wand %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-disselhoff26a %I PMLR %P 25483--25509 %U https://proceedings.mlr.press/v306/disselhoff26a.html %V 306 %X Why do neural networks generalize well on natural data? Natural data originates from processes subject to specific physical constraints, such as temporal and spatial invariance, that make it easier to learn. We investigate the sufficiency of these properties using 2D cellular automata as a controlled testbed: systems that are perfectly local, symmetric, and deterministic. We find that these conditions alone are not sufficient to predict the $k$-step evolution of a cellular automaton. We then examine smoothness (average sensitivity) as an additional criterion and find it predictive but still incomplete. Finally, we introduce a circuit complexity perspective, hypothesizing that natural functions are computable by small circuits. Junta coefficients, measuring the concentration of Fourier weight by interaction degree, provide a tighter predictor of learnability and a correspondence to combinatorial complexity. Across architectures (CNNs, transformers, MLPs), learnable functions are predominantly those with spectral weight concentrated at low degrees and therefore low complexity. These results would be consistent with the hypothesis that natural data is learnable because natural dynamics filters out complex, high-degree interactions.
APA
Disselhoff, J. & Wand, M.. (2026). Probing the Inductive Bias of Neural Networks through Learning Random Cellular Automata. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:25483-25509 Available from https://proceedings.mlr.press/v306/disselhoff26a.html.

Related Material