Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks
This addresses the challenge of algorithmic execution in neural networks, offering a theoretical framework for exact generalization, though it is incremental as it builds on existing NTK analysis.
The paper tackled the problem of neural networks failing to generalize perfectly to discrete operations like arithmetic by showing that two-layer networks in the infinite-width limit can be trained to execute binary-encoded algorithmic instructions exactly, achieving high probability success on tasks such as binary addition, multiplication, and Turing-complete instructions using only logarithmically many training data.
Neural networks are known for their ability to approximate smooth functions, yet they fail to generalize perfectly to unseen inputs when trained on discrete operations. Such operations lie at the heart of algorithmic tasks such as arithmetic, which is often used as a test bed for algorithmic execution in neural networks. In this work, we ask: can neural networks learn to execute binary-encoded algorithmic instructions exactly? We use the Neural Tangent Kernel (NTK) framework to study the training dynamics of two-layer fully connected networks in the infinite-width limit and show how a sufficiently large ensemble of such models can be trained to execute exactly, with high probability, four fundamental tasks: binary permutations, binary addition, binary multiplication, and Subtract and Branch if Negative (SBN) instructions. Since SBN is Turing-complete, our framework extends to computable functions. We show how this can be efficiently achieved using only logarithmically many training data. Our approach relies on two techniques: structuring the training data to isolate bit-level rules, and controlling correlations in the NTK regime to align model predictions with the target algorithmic executions.