Compression Selects Structure: Why Compression Favors Generalizable Solutions in Group-Operation Tasks

Neural networks can fit the same training data yet generalize differently. We study why compression can favor reusable rules, using finite-group operations to test generalization to unseen combinations. We introduce *effective gate complexity* (EGC), measuring the structure needed to reproduce a complete prediction map within a prescribed fixed-depth ReLU architecture. EGC minimizes the number of switching and everywhere-active gates in one-hidden-layer networks with separate operand embeddings and, at arbitrary fixed ReLU depth, records the coordinatewise minimal budgets of affine rank and layerwise ReLU responses retained across equivalent realizations and exact structural reductions. For one-hidden-layer networks, we establish a uniform finite-sample generalization bound in terms of training error and EGC. Every true group law of order $Q$ has EGC $O(\sqrt{Q}\log Q)$, whereas fits that generalize poorly require EGC $\Omega (Q/\log Q)$ with high probability under constant-density random sampling. This separation yields a nonempty compression window for sufficiently large $Q$ and ensures that minimum-EGC fits generalize. We further extend the counting and generalization bounds to multilayer EGC budgets at any fixed ReLU depth. On the stated machine-learning group families at the specified fixed ReLU depths with hidden widths at least logarithmic in $Q$ and bounded width ratios, near-optimality of the quadratically regularized objective controls parameter norms and training error, yielding exact low-EGC realizations of complete prediction maps in the original architecture and hence generalization. Uniformly over an explicit weight-decay interval, an objective-gap tolerance proportional to the decay strength permits sparse sampling with $n=\Theta (Q^{2-\beta })$, yielding held-out error $O(Q^{\beta -1/8})$ with high probability for $0\le \beta <1/8$. These guarantees apply throughout the prescribed near-optimal region, without further optimizer-dependent selection. Experiments on modular addition illustrate the connection between lower regularized objective values, smaller verified EGC budgets, and improved held-out accuracy.