The Mismatch between Neural Affinity and Symbolic Simplicity

A large body of work on simplicity bias shows that neural networks favor simple functions. Because the target functions in many real problems are expected to be highly structured, this preference is believed to aid generalization. But does this simplicity bias still hold in the space of symbolic rules? In other words, is the "simplicity" that networks prefer the "simplicity" that humans find easy to understand? We prove a mismatch between the two and establish that it is irreducible: almost every Boolean function has a longer description than parity yet sits at a lower frequency, and even at matched frequency, description lengths range from logarithmic to exponential. Experiments confirm the mismatch: what is cheap to describe is not what is cheap to learn. Even when a compact parity rule and a randomly drawn function fit the training labels equally well, MLPs learn the random function first, and so does a Transformer. These findings challenge the expectation that symbolically simple targets benefit from neural simplicity bias: short symbolic rules can instead face a learning disadvantage.