Research map / Learning theory and algorithms / Kernels and regression theory
Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows via NTK theory that ensembles of infinite-width two-layer ReLU networks trained on logarithmically many orthonormal template examples can exactly execute binary permutation, addition, multiplication, and SBN instructions.
Problem
Whether neural networks trained by gradient descent can learn to execute discrete algorithmic instructions (arithmetic, permutations, Turing-complete SBN) exactly, generalizing perfectly to unseen binary inputs.
Approach
Structure training data as orthonormal block-wise templates capturing local bit-level rules, so the NTK predictor's sign pattern encodes the correct output; ensembles of such networks are averaged and rounded to get exact execution with high probability.
Key results
- Theorem shows NTK predictor sign information is preserved for permutation, addition, multiplication, and SBN templates under an unwanted-correlation assumption.
- Ensemble complexity scales as O(l^2) for permutation, addition, and multiplication, where l is bit length.
- Numerical validation of constructive instructions is reported for bit lengths up to l=10.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Structure training examples as orthonormalized local algorithmic templates | Two-layer fully connected network in the infinite-width NTK regime · Binary permutations, addition, multiplication, and SBN instructions | exact execution | Helped |
| Average independently trained models before rounding their outputs | Two-layer fully connected network ensemble · Binary algorithmic instructions | post-rounding accuracy: 1-δ | Helped |
| Use orthonormalized template encoding and rounding | NTK predictor · Binary permutations, addition, and multiplication | numerical correctness: ℓ=10 | Helped |
Limitations
- Bounded memory: input dimension fixed, so longer inputs require retraining; no length generalization for variable-length inputs.
- Assumes orthogonal training data and explicit access to primitive instructions.
- Empirical verification of ensemble complexity is limited to permutation task with 50,000 hidden units.
Experimental setup
Datasets: synthetic template instruction sets for binary permutation, addition, multiplication, SBN
Metrics: post-rounding exact accuracy ensemble complexity NTK predictor sign correctness
Baselines: Neural GPU NALU NAU/NMU Transformers with scratchpads
Builds on: Neural Tangent Kernel Neural GPU NALU NAU/NMU
Closest papers by meaning
- Auto-Regressive Next-Token Predictors are Universal Learners (ICML 2024 · similarity 0.85)
- Taming Binarized Neural Networks and Mixed-Integer Programs (AAAI 2024 · similarity 0.85)
- Emergence in non-neural models: grokking modular arithmetic via average gradient outer product (ICML 2025 · similarity 0.84)
- Uncovering a Universal Abstract Algorithm for Modular Addition in Neural Networks (NeurIPS 2025 · similarity 0.84)
- Arithmetic Without Algorithms: Language Models Solve Math with a Bag of Heuristics (ICLR 2025 · similarity 0.84)
- KLay: Accelerating Arithmetic Circuits for Neurosymbolic AI (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.