Technical Summary: Sequential Group Composition

Problem Statement

The paper addresses a fundamental question in deep learning: how do neural networks trained on sequential data acquire the ability to perform structured operations, such as arithmetic, geometric transformations, and algorithmic computations? While natural data often exhibits symmetry (e.g., commutative or non-commutative structures), it remains unclear how standard architectures learn to compose transformations rather than merely recognize them.

To investigate this, the authors introduce the Sequential Group Composition Task. In this task, a neural network receives a sequence of $k$ elements from a finite group $G$, encoded as real vectors, and must predict the encoding of their cumulative product $g_1 \cdot g_2 \cdots g_k$.

• Input: A sequence of encoded elements $x_{g} = (x_{g_1}, \dots, x_{g_k}) \in \mathbb{R}^{k|G|}$.
• Target: The encoding of the product $x_{g_1 \cdots g_k} \in \mathbb{R}^{|G|}$.
• Constraints: The task is inherently nonlinear (cannot be solved by linear models) and, for non-Abelian groups, order-sensitive. The number of possible input sequences grows exponentially with $k$, making memorization infeasible for efficient scaling; the network must uncover the underlying algebraic structure.

Methodology

The authors employ a combination of harmonic analysis over finite groups, dynamical systems theory for neural network training, and constructive complexity analysis.

1. Mathematical Framework

• Group Representations: The task is analyzed using the representation theory of finite groups. Group elements are encoded via the orbit of a fixed vector $x$ under the regular representation.
• Fourier Analysis: The authors utilize the group Fourier transform, which decomposes signals into irreducible representations (irreps). This allows the task to be viewed as learning specific frequency components (irreps) of the group.
• Loss Function: The network is trained to minimize the mean squared error (MSE) between the predicted and actual encodings of the group product.

2. Learning Dynamics (Two-Layer Networks)

For two-layer networks with polynomial activations trained under vanishing initialization, the authors apply the Alternating Gradient Flow (AGF) framework (Kunin et al., 2025).

• Dynamics: Training proceeds in a stepwise manner. Neurons alternate between "dormant" (near origin) and "active" (far from origin) states.
• Utility Maximization: Dormant neurons compete to align with the most informative directions in the residual error. The authors prove that the "utility" of a neuron is maximized when its weights align with a specific irreducible representation $\rho^*$ of the group.
• Selection Order: The order in which irreps are learned is determined by the Fourier statistics of the encoding vector $x$. Specifically, the network greedily selects the irrep $\rho$ that maximizes a score involving the operator norm of the Fourier coefficient $\|\hat{x}[\rho]\|$ and the dimension $n_\rho$.
• Cost Minimization: Once active, neurons rapidly increase in norm to minimize the loss. The authors show that to perfectly learn the task, the network must effectively implement a "sigma-pi-sigma" structure, canceling out extraneous terms to isolate the interaction term corresponding to the group product.

3. Architectural Analysis

The paper compares the efficiency of different architectures in solving the task:

• Two-Layer MLPs: To perfectly learn the task, these networks require a hidden width $H$ that scales exponentially with the sequence length $k$ (specifically $H \sim O(k 2^k)$). This is due to the need to coordinate a large number of neurons to cancel non-interaction terms.
• Recurrent Neural Networks (RNNs): By exploiting the associativity of group operations, RNNs can compose elements sequentially. The authors construct a solution where the RNN learns the task with a hidden width that is constant with respect to $k$ (scaling only with the group size $|G|$).
• Deep Feedforward Networks: Multilayer networks can compose adjacent pairs in parallel (divide-and-conquer strategy). This reduces the required depth to logarithmic in $k$ ($O(\log k)$) while maintaining polynomial width.

Key Results

1. Non-Linearity Requirement: The task cannot be solved by any linear map, regardless of depth, because it requires nonlinear interactions between inputs to compute the product.
2. Stepwise Feature Learning: In two-layer networks under vanishing initialization, the network learns irreducible representations one at a time. The order is dictated by the encoding statistics, with a systematic bias toward learning lower-dimensional irreps first, an effect that strengthens as sequence length $k$ increases.
3. Exponential Width Barrier: Two-layer networks require exponential hidden width ($H \geq (k+1)2^{k-1} \lfloor |G|/2 \rfloor$ for cyclic groups) to perfectly solve the task. This is proven to be optimal for this architecture class.
4. Efficiency of Depth: Deeper architectures (RNNs and Deep MLPs) can solve the task with significantly better scaling. RNNs achieve linear time complexity ($k$ steps) with constant width, while Deep MLPs achieve logarithmic depth ($\log k$ layers) with polynomial width, leveraging the associativity of the group operation.
5. Empirical Validation: Experiments on cyclic and dihedral groups confirm the theoretical predictions. Two-layer networks exhibit "staircase" loss curves corresponding to the sequential acquisition of irreps. RNNs and deep networks demonstrate the ability to learn the task with much smaller parameter counts compared to shallow networks.

Significance and Claims

The paper positions the sequential group composition task as a tractable window into the mechanics of deep learning. Its primary contributions are:

• Analytical Tractability: It provides a precise, first-principles derivation of how neural networks learn to compose transformations, moving beyond empirical observation to a theoretical understanding of feature emergence.
• Universality of Dynamics: It establishes a universal mechanism where networks learn group structures via Fourier features in a greedy, stepwise order determined by input statistics.
• Role of Depth: It offers a rigorous characterization of how depth improves efficiency. While shallow networks are limited by exponential width requirements, deeper architectures can exploit algebraic properties (associativity) to find efficient compositional solutions.

The authors note that their theoretical results for two-layer networks are derived under controlled settings (finite groups, polynomial activations, vanishing initialization). While they provide empirical evidence that these dynamics persist with standard activations (like ReLU and Tanh) and in deeper networks, they acknowledge that a full dynamical theory for recurrent and deep networks remains an open challenge. The work serves as a foundational step toward a mathematical theory of how neural networks learn from sequential data, with potential extensions to semiautomata and formal grammars.