acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 has EGC , whereas fits that generalize poorly require EGC with high probability under constant-density random sampling. This separation yields a nonempty compression window for sufficiently large 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 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 , yielding held-out error with high probability for . 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.

Primary area:
learning theory
Keywords:
generalization, compression, effective gate complexity, weight decay

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_Leh6OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies why compression favors generalizable rule-based solutions over memorizing solutions in finite-group operation tasks, and introduces Effective Gate Complexity (EGC) to measure the minimum structural complexity required to realize a complete prediction map. Theoretically, the authors first derive uniform generalization bounds from low EGC and show that the true group law has substantially lower EGC than poorly generalizing fits, thereby establishing a nonempty compression window. They further prove that, for specified group families and fixed-depth ReLU networks, every parameter vector sufficiently close to the global optimum of a quadratically regularized objective has a complete prediction map admitting a low-EGC realization, and hence generalizes. Experiments on modular addition over Z127\mathbb{Z}_{127} show that lower regularized objective values are associated with higher held-out accuracy and smaller verified EGC upper bounds, providing qualitative support for the proposed compression mechanism.

Critical strengths
  1. The paper presents an interesting perspective on the relationship between compression and generalization. Rather than treating compression only as a generic complexity control, it identifies a task-dependent structural notion that can separate the true group law from poorly generalizing fits, which gives the framework a clear theoretical interpretation.

  2. The experimental section is handled with considerable care. The authors verify exact agreement of complete prediction maps over the full input domain and explicitly distinguish certified EGC upper bounds from true EGC, which makes the empirical evidence more reliable despite its limited scope.

Critical weaknesses
  1. The theoretical guarantees are interesting but rely on a fairly specific set of assumptions, and the scope of some of the broader claims could be delineated more clearly. The strongest results depend on particular group families, representations, architectures, width and finite-size conditions, and quantitative near-global optimality, so the generality of the conclusions is narrower than the title and some of the surrounding discussion may suggest.

  2. The empirical results provide only indirect support for the main theoretical mechanism. The experiments do not verify the near-optimality condition required by the main theorem, and the reconstruction procedure certifies only EGC upper bounds. Thus, the results are best interpreted as qualitative evidence rather than a direct validation of the theoretical guarantees.

Questions for authors
  1. Can the authors provide any quantitative evidence that the experimental checkpoints are close to the near-optimal region required by Theorem 4.1? In particular, is there any computable lower bound, relaxation, or certificate for JA∗J_A^\ast that allows one to estimate J(θ)−JA∗J(\theta)-J_A^\ast? This would materially affect how strongly the experiments support the main theoretical mechanism.

  2. Can the authors clarify the finite-QQ regime in which Theorem 4.1/4.2 becomes non-vacuous? In particular, for the experimental setting Q=127Q=127, which finite-size conditions are satisfied or violated, and what are the main conditions determining the asymptotic threshold? This would help assess the quantitative scope of the theoretical guarantees.

A clear response to these questions would help strengthen my confidence in the paper and may lead to a higher rating.

Reviewer_rxa2OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies why compression and weight decay lead to rule-like solutions on finite-group tasks such as modular addition. effective gate complexity (EGC) is then proposed to do this study, and a small experiment is included.

Critical strengths
  1. The idea itself is clear and the question is interesting. The paper describes a pipeline to solve the problem and prove some theorems.
  2. The weight-decay result does not depend on the optimizer, and the experiments check exact matches carefully on the full input domain.
Critical weaknesses
  1. The paper is relatively hard to read and follow. For example, some terms are defined in the appendix while used in the main context, which makes it quit hard to follow some claims.
  2. It is unclear how useful in practice of this method. The experiment setting is relatively simple and limited.
Questions for authors
  1. could you add more empirical results or some discussions on non-abelian groups and on several values of Q?
  2. How is EGC different from other compression-based explanations of grokking that the paper cites?
Reviewer_wd6DOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The authors introduce the effective gate complexity (ECG) as a measure for generalization. Specifically, they do so for group-operation tasks in single and multi-layer ReLU networks postulating generalization bounds for both. They further show that quadratic weight decay allows sparse training set sampling. The theory is evaluated empirically on modular addition.

Critical strengths

Extensive Theoretical Treatment

The text covers its theoretical groundwork very precisely and extensively, which ensures the validity of the derived generalization bounds.

Critical weaknesses

Lack of Clarity

The text is written very densely and, at times, packed with inline symbols. This makes it hard to follow the reasoning. Furthermore, the authors fail in providing intuition which could easily be recovered, e.g., by being more verbose in explaining key terms such as the central EGC or, better yet, making use of illustrations.

Questionable Practical Relevance

The authors treat (mainly binary) group operation tasks and validate their theoretical ground work on modular addition. If I understood the text correctly, the derived generalization bounds also do only hold for this group operation setting with ReLU networks. It thereby seems difficult to argue that the idea transfers easily to more realistic settings where underlying group actions may not be readily inferred. The text should, at least, discuss its finding's transferability to other problems more clearly and address limitations. Correspondingly, the practical evaluation is rather thin and only makes use of an already studied topic (modular addition) with regards to "grokking" (e.g., Nanda et al., ICLR 2023; Gromov, arXiv 2023). The latter may render it a valid point of reference but it still prompts the question where the practical contribution beyond the established literature lies.

Minor

The authors use a numbered citation style while the formatting instructions state: "Citations within the text should be based on the natbib package and include the authors' last names and year (with the ''et~al.'' construct for more than two authors).". This leads to more available space in this compared to other submissions that complied with the formatting guide lines.

Recommendation:

I rate this paper with a Weak Rejection, on the grounds of the, in my judgement, missing practical relevance and lack of clarity. Theory and notation dense prose aside, I find it a very hard task to extract the paper's key contributions and, only with great difficulty, could follow the line of thought.

Questions for authors
  • Can the authors, clearly and in simple terms, explain the most important concepts, e.g.,

    • EGC
    • Complete prediction map
  • Can the authors discuss the extent to which their generalization bounds apply to practical problems?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.