Sequential Group Composition: A Window into the Mechanics of Deep Learning

How do neural networks trained over sequences acquire the ability to perform structured operations, such as arithmetic, geometric, and algorithmic computation? To gain insight into this question, we introduce the sequential group composition task. In this task, networks receive a sequence of elements from a finite group encoded in a real vector space and must predict their cumulative product. This task can be order-sensitive and cannot be solved by a linear model. Our analysis isolates the roles of the group structure, encoding statistics, and sequence length in shaping learning. We prove that two-layer networks from vanishing initialization learn this task one irreducible representation of the group at a time in an order determined by the Fourier statistics of the encoding. To perfectly learn the task, these networks require a hidden width exponential in the sequence length $k$. In contrast, we construct deeper architectures that exploit associativity to dramatically improve this scaling: recurrent neural networks can compose elements sequentially in $k$ steps, while multilayer networks can compose adjacent pairs in parallel in $\log k$ layers. Overall, the sequential group composition task offers a tractable window into the mechanics of deep learning.

Despite the popularity of neural networks within AI, we do not understand what and how they learn. In our work, we study how neural networks learn to solve problems that involve composing a sequence of elements following prescribed algebraic rules. These tasks are simple but illustrative, since they require the model to build an internal understanding of the underlying rules, rather than just memorize examples. We show that, as training progresses, the network learns these rules step by step, forming increasingly organized internal representations. Our tools come from abstract algebra, and involve a far-reaching generalization of methods originating in signal processing (the “Fourier Transform”). The results help explain how artificial intelligence systems discover structure in data, and offer a clearer picture of how complex reasoning-like behavior can emerge from learning.